Kth smallest element in array
Given an set of numbers in non-sorted order, find the Kth smallest element. Kth smallest element means there are N-K-1 elements in set which are greater than the desired element.
We can solve this problem in two simple steps:
1. sort the input set.
2. Scan the array till Kth element, it gives us the Kth smallest element in array.
Thing to ponder upon here is can we do better? Can we avoid the second step? Can we reduce the size of input to be sorted or not sorting the input at all? Answer to all above questions is Yes. Think Quick sort.
Algorithm to find Kth smallest element
Quick sort does not completely sorts two sub arrays when it gives us the correct position of pivot.By property of quick sort we know that all elements which are on left side of pivot are less than pivot.
Let’s say we have pivot swapped with jth element of the input set, so there are j elements which are less than pivot. Can we use this information to find Kth smallest element? Absolutely yes.
If j is less than K, then we have smaller left subset and we need to look into right subset of the input to get the Kth smallest element. So we look (K-j)th smallest element in the right subset.
Here we have not sorted left or right subset of the input and still we reduced the candidate by almost half.
If j is more than K, then we need to look in left subset of input. Here we have discarded the right subset of the input.
As we are doing partitions and calculating the position of pivot, we don’t need to scan the array afterwards. As soon as position of pivot is equal to K, we got element.
Let’s say we have an array with following elements 4,2,1,7,5,3,8,10,9,6 and we need to find fifth smallest element in this array. In this example output will be 5.
We have pivot as 1st element i.e 4 and we divide the remaining array in such a way that we find the correct position of 4.
Once 4 is in correct position, all the elements on left side are less than pivot i.e 4 and on right side, are greater than pivot.
Now check the position of pivot, if it is K-1 (array is represented as zero base index), then pivot is our element.
Here final position of 4 after first execution of quick sort function will be index 3.
Since pivot position is less than K-1 i.e 4, we need to look for element in right side of the pivot.
Notice that we are not reducing K as pivot position is given w.r.t whole array and not w.r.t sub-array under consideration.
In second iteration, 5 will be pivot. After second execution of quick sort array will look as mentioned above only thing is our pivot position is change.
pivot index is now 4 which is equal to K-1. Hence our 5th smallest element in this array is 5. Note that we have not sorted the complete array.
Video to explain Kth smallest element algorithm
As we are reducing the candidates by half, our equation of complexity becomes :
T(n) = T(n/2) + T(n/2)
If we directly take Master theorem, complexity becomes O(nlogn).
There is a catch here, if input is in sorted order, then worst case complexity becomes O(n^2)
So we can first scan input and if it is sorted, we can simply count the elements and find out the Kth smallest element. Please refer to previous post for details how we can select pivot so that quick sort does not go for worst case performance irrespective of the nature and order of input.
Finding Kth smallest element is typical application of quick sort. We can apply quick sort algorithm in any problem where we need to find out relative position of an element w.r.t others without actually sorting the elements of input.