We recommend to read following post as a prerequisite of this post.
K’th Smallest/Largest Element in Unsorted Array | Set 1
Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.
Examples:
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10
We have discussed three different solutions here.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
In this post method 4 is discussed which is mainly an extension of method 3 (QuickSelect) discussed in the previous post. The idea is to randomly pick a pivot element. To implement randomized partition, we use a random function, rand() to generate index between l and r, swap the element at randomly generated index with the last element, and finally call the standard partition process which uses last element as pivot.
[ad type=”banner”]Following is implementation of above Randomized QuickSelect.
JAVA
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20find%20k’th%20smallest%20element%20in%20expected%0A%2F%2F%20linear%20time%0Aclass%20KthSmallst%0A%7B%0A%20%20%20%20%2F%2F%20This%20function%20returns%20k’th%20smallest%20element%20in%20arr%5Bl..r%5D%0A%20%20%20%20%2F%2F%20using%20QuickSort%20based%20method.%20%20ASSUMPTION%3A%20ALL%20ELEMENTS%0A%20%20%20%20%2F%2F%20IN%20ARR%5B%5D%20ARE%20DISTINCT%0A%20%20%20%20int%20kthSmallest(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20k)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20k%20is%20smaller%20than%20number%20of%20elements%20in%20array%0A%20%20%20%20%20%20%20%20if%20(k%20%3E%200%20%26%26%20k%20%3C%3D%20r%20-%20l%20%2B%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Partition%20the%20array%20around%20a%20random%20element%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20get%20position%20of%20pivot%20element%20in%20sorted%20array%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20pos%20%3D%20randomPartition(arr%2C%20l%2C%20r)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20position%20is%20same%20as%20k%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(pos-l%20%3D%3D%20k-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20arr%5Bpos%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20position%20is%20more%2C%20recur%20for%20left%20subarray%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(pos-l%20%3E%20k-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20kthSmallest(arr%2C%20l%2C%20pos-1%2C%20k)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Else%20recur%20for%20right%20subarray%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20kthSmallest(arr%2C%20pos%2B1%2C%20r%2C%20k-pos%2Bl-1)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20k%20is%20more%20than%20number%20of%20elements%20in%20array%0A%20%20%20%20%20%20%20%20return%20Integer.MAX_VALUE%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Utility%20method%20to%20swap%20arr%5Bi%5D%20and%20arr%5Bj%5D%0A%20%20%20%20void%20swap(int%20arr%5B%5D%2C%20int%20i%2C%20int%20j)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20arr%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Standard%20partition%20process%20of%20QuickSort().%20%20It%20considers%0A%20%20%20%20%2F%2F%20the%20last%20element%20as%20pivot%20and%20moves%20all%20smaller%20element%20%0A%20%20%20%20%2F%2F%20to%20left%20of%20it%20and%20greater%20elements%20to%20right.%20This%20function%0A%20%20%20%20%2F%2F%20is%20used%20by%20randomPartition()%0A%20%20%20%20int%20partition(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%20arr%5Br%5D%2C%20i%20%3D%20l%3B%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%20l%3B%20j%20%3C%3D%20r%20-%201%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swap(arr%2C%20i%2C%20j)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20swap(arr%2C%20i%2C%20r)%3B%0A%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Picks%20a%20random%20pivot%20element%20between%20l%20and%20r%20and%20%0A%20%20%20%20%2F%2F%20partitions%20arr%5Bl..r%5D%20arount%20the%20randomly%20picked%20%0A%20%20%20%20%2F%2F%20element%20using%20partition()%0A%20%20%20%20int%20randomPartition(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20r-l%2B1%3B%0A%20%20%20%20%20%20%20%20int%20pivot%20%3D%20(int)(Math.random())%20%25%20n%3B%0A%20%20%20%20%20%20%20%20swap(arr%2C%20l%20%2B%20pivot%2C%20r)%3B%0A%20%20%20%20%20%20%20%20return%20partition(arr%2C%20l%2C%20r)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%20to%20test%20above%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20KthSmallst%20ob%20%3D%20new%20KthSmallst()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%203%2C%205%2C%207%2C%204%2C%2019%2C%2026%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%2Ck%20%3D%203%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22K’th%20smallest%20element%20is%20%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ob.kthSmallest(arr%2C%200%2C%20n-1%2C%20k))%3B%0A%20%20%20%20%7D%0A%7D%0A%2F*This%20code%20is%20contributed%20by%20Rajat%20Mishra*%2F%0A” message=”java” highlight=”” provider=”manual”/]Output:
K'th smallest element is 5
Time Complexity:
The worst case time complexity of the above solution is still O(n2). In worst case, the randomized function may always pick a corner element. The expected time complexity of above randomized QuickSelect is Θ(n), see CLRS book or MIT video lecture for proof. The assumption in the analysis is, random number generator is equally likely to generate any number in the input range.