Wednesday, October 30, 2013

How to Get The Kth Smallest Element in an Array


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


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)
   while (uA[j] > uA[pivot] && i < j)
   if (i < j) {
    tmp = uA[i];
    uA[i] = uA[j];
    uA[j] = tmp;

  if (i > j || uA[i] > uA[pivot]) {
  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]);

No comments :