Algo #121 : Quick Select Algorithm

Problem Statement : 
         Find the kth smallest element in an unsorted array.

Input : 
Array : [ 7 , 5 , 4 , 3, 2, 8 , 1 ]
and k= 3  (kth smallest element)

Output: 3

PS: No duplicate elements in the array

Solution : 

One of the simplest method to solve the above problem would be to sort and then find the kth smallest element. But sorting would take O(nlogn) and again O(n) to find the kth smallest element.

Now the question is can we do better than this ? Yes we can.

We can use even Min-heap to store the elements and pop k-times to get the k-th smallest element.

Quick Select Algorithm : 
In this post we will discuss Quick Select Technique which is very much similar to Quicksort.
We know that elements to the left of pivot are smaller and elements to the right of pivot are greater than pivot.

Lets take an example to demonstrate this
Array : [ 7 , 5 , 4 , 3, 2, 8 , 1 ] and k= 3
Below i will walk you through changes happening in the array , which will finally return kth-smallest element. Note we are considering the last element of the array (coloured green ) as pivot

Fig1 : Demonstration the steps on Quick Select

Below is the code implementation :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public int findKSmallest(int[] arr, int k, int l, int r) { int len = arr.length; if (k > 0 && k <= len) { int index = partition(arr, l, r); if (index + 1 == k) return arr[index]; else if (index < k) return findKSmallest(arr, k, index + 1, r); else return findKSmallest(arr, k, l, index - 1); } return -1; } private int partition(int[] arr, int l , int r){ int pivotValue = arr[r]; int storeIndex=l,i=l; for (;i < r; i++ ) { if (arr[i] <= pivotValue) swap(arr, i, storeIndex++); } if(arr[storeIndex] > arr[r]) swap(arr, r, storeIndex); //System.out.println(Arrays.toString(arr)); return storeIndex; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {7,5,4,3,2,8,1}; int k = 3; KQuickSelect sortObj = new KQuickSelect(); int data = sortObj.findKSmallest(arr, k, 0, arr.length-1); System.out.println(data); }

PS: The above code will work fine for non-duplicate elements. For duplication elements you can use Min-Heap technique.

Please post your suggestions and comments.
Happy Coding !! :)