Given an array of numbers, how do we efficiently find the Kth smallest number in it?
This problem is also called the selection problem. Widely used in order statistic (Find the smallest, biggest, median, top K elements etc…)
For example in the array [6, 1, 9, 8, 3, 5, 4] the third smallest element is 4.
An obvious approach could be to sort the entire array and return the element array[K-1]. But this approach takes O(n log n) time in the worst case (Sorting time).
Another simple approach could be to perform first K steps in either insertion sort or selection sort which gives us the required element. But this approach takes time proportional to K.
Can we do better than this?
We can use the partition method used in Quick sort to solve this problem. The partition method divides the array into two parts based on a pivot element. The pivot element is in it’s correct position. All the elements to the left of it are less than or equal to pivot, and all the elements to the right of it are greater than pivot. Finally it returns the pivot position.
We can compare the pivot with K. If it is equal we are done!. If pivot is less than K, we need to search the right-side partition otherwise we need to search the left side partition.
Here is the Java implementation of the above algorithm.