Skip to content

Instantly share code, notes, and snippets.

@jitsceait
Last active August 29, 2015 14:00
Show Gist options
  • Save jitsceait/9635513ac489d1bf9d85 to your computer and use it in GitHub Desktop.
Save jitsceait/9635513ac489d1bf9d85 to your computer and use it in GitHub Desktop.
This program finds Kth smallest element in an unsorted array
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int A[], int start, int end){
int i= start+1;
int j = i;
int pivot = start;
for(; i<end; i++){
if(A[i]<A[pivot]){
swap(&A[i],&A[j]);
j++;
}
}
if(j<=end){
swap(&A[pivot],&A[j-1]);
}
for(i=0;i<10;i++){
printf("%d ", A[i] );
}
printf("\n");
return j-1;
}
void quick_sort(int A[], int start, int end, int K){
int part ;
if(start <end) {
part = partition(A, start, end);
if(part == K-1){
printf("kth smallest element : %d" , A[part]);
}
if(part>K-1){
quick_sort(A, start,part, K);
}
else{
quick_sort(A, part+1, end, K);
}
}
return;
}
/* Driver program for the function written above */
int main(){
int array[] = {4,2,1,7,5,3,8,10,9,6};
int n = sizeof(array)/sizeof(array[0]);
quick_sort(array,0, n, 4);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment