Selecting k smallest or largest elements

We are interested in the k smallest elements themselves and not the ordering relation between them. Assuming partitioning just completed let’s denote set of elements that are before pivot (including pivot itself) by L and set of elements that are after pivot by H. According to partition definition L contains |L| (where |X| denotes number of elements in a set X) smallest elements. If |L| is equal to k we are done. If it is less than k than look for k smallest elements in L. Otherwise as we already have |L| smallest elements look for k - |L| smallest elements in H.

Finding position of kth smallest element is enough as elements up to that are are smaller than the element at kth position.

int kthSmallestElement(int[] a, int low, int high, int k) {
  if (low > high)
   return -1;
  int i = low;
  int j = high;
  int h;
  // comparision element

  int pivotIndex = (low + high) / 2;
  int x = a[pivotIndex];

  // partition
  do {
   while (a[i] < x)
    i++;
   while (a[j] > x)
    j--;
   if (i <= j) {
    h = a[i];
    a[i] = a[j];
    a[j] = h;
    
    //Tracking pivot index is important.
    if (x == a[i]) {
     pivotIndex = i;
    } else if (x == a[j]) {
     pivotIndex = j;
    }
    i++;
    j--;
   }
  } while (i <= j);

  if (pivotIndex == k) {
   return a[pivotIndex];
  } else if (k <= j) {
   return kthSmallestElement(a, low, j, k);
  } else
   return kthSmallestElement(a, i, high, k);
 }

Good explanation is here : http://42bits.wordpress.com/2010/04/17/find-kth-minimum-in-a-unsorted-array/