How to Get The Kth Smallest Element in an Array

Problem:

As the title said, "How to get the kth smallest element in an array?"
This array could be totally unordered.

Solution:

Most intuitive method for this problem would be sort the array, then return the kth value of the array, which cost O(NlogN) + O(1), which is O(NlogN). But there is O(N) algorithms for average case called Selective Algorithms.

It's very like Quick-Sort Algorithm, but this one always cuts the array in two, and choose the one we need. So it would be like:

T(n) = T(P) + O(n) , P is one of (1 , n)

 For average, P would be n/2, since we choose it randomly, then we could have T(n) = O(n).

If K is n/2, then this problem turns to be finding the medium element of array.

This is a very popular interview question, so have fun.

---

Source Code:

private int getKthSmallestElement(int[] uA, int start, int end, int kth) {
  print(uA, start, end);
  Random r = new Random();
  int pivot = start + r.nextInt(end - start + 1);
  System.out.println(String.format("Pivot Element %d", uA[pivot]));
  int tmp = uA[start];
  uA[start] = uA[pivot];
  uA[pivot] = tmp;
  pivot = start;
  int i, j;
  for (i = start + 1, j = end; i < j;) {
   while (uA[i] <= uA[pivot] && i < j)
    i++;
   while (uA[j] > uA[pivot] && i < j)
    j--;
   if (i < j) {
    tmp = uA[i];
    uA[i] = uA[j];
    uA[j] = tmp;
    i++;
    j--;
   }
  }

  if (i > j || uA[i] > uA[pivot]) {
   i--;
  }
  tmp = uA[i];
  uA[i] = uA[pivot];
  uA[pivot] = tmp;
  pivot = i;

  System.out.println(String.format("(Start, End) : (%d %d)", start, end));
  print(uA, start, end);
  System.out.println(String.format("(i, j) : (%d %d)", i, j));
  System.out.println(String.format("Pivot: %d\n", pivot));
  if (pivot + 1 == kth)
   return uA[pivot];
  else if (pivot + 1 > kth) {
   return getKthSmallestElement(uA, start, pivot - 1, kth);
  } else
   return getKthSmallestElement(uA, pivot + 1, end, kth);
 }

 private void print(int[] array, int start, int end) {
  for (int i = start; i <= end; i++)
   System.out.print(" " + array[i]);
  System.out.println();
 }