## 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();
}
```