Apr 19, 2011

find kth smallest element in an array

void kthsmallest(int k, int l, int u)
{
if(l>= u)
return;

//partition
int m=l;
for(int i=l+1; i<= u; i++)
{
if(arr[i] < arr[l])
{
//swap them
int t=arr[i];
arr[i]=arr[m+1];
arr[m+1]=t;
m++;
}
for(int j=0;j< 8;j++)
cout << " " << arr[j];
cout << " m= " << m << " i= " << i << endl;
}
//swap l, m
int t=arr[m];
arr[m]=arr[l];
arr[l]=t;

for(int i=0;i< 8;i++)
cout << " " << arr[i];
cout << " [" << arr[m] << "] is now correctly placed at position " << m ;
cout << endl;
/*
if(m==k)
cout << k << "th smallest element is " << arr[m] << endl;
*/
//recursively call qsort
if(k< m)
kthsmallest(k, l, m-1);
if(k> m)
kthsmallest(k, m+1, u);
}

//program end

No comments: