QuickSelect is a selection algorithm that finds the kth smallest number from a list. QuickSelect is O(n) algorithm. I built a simple prototype to verify that QuickSelect works in linear time.
QuickSelect uses a random pivot to partition the array. The items to the left of the pivot are lesser than the pivot. The items to the right of the pivot are greater than the pivot. …