Randomized selection to return the i'th order statistic

Suppose you have an unsorted array of size N and that you want to determine the ith order statistic for the same array. This is nothing but the ith smallest element in the array. While a simple way to do this would be to sort the array using an efficient sorting technique like say merge sort in O(NlogN) and then return the element in the ith position in O(1) time, apparently, there exists a much faster algorithm to achieve the same end. It's called QuickSelect.

int quickSelect ( int[] a , int lb , int ub , int i ) throws Exception {

if ( lb >= ub )

throw new Exception ("invalid i");

p = partition ( a , lb , ub );

if ( p > i )  //look to the left

    quickSelect ( a , lb , p-1 , i );

if ( p < i )  //look to the right

    quickSelect ( a , p + 1 , ub , i - p );

if ( p == i )

    return a[p];

}

Now, what is randomized here is the selection of the pivot in the partition routine. The pivot for this pass of the quickSelect is chosen randomly among ub-lb elements of the array and the partitioning is done around this pivot.

The difference between quicksort and the quickselect routine is that while quicksort recursively applies the partition toboth halves of the sub-array, quickselect determines which side of the pivot the ith order statistic resides and applies the recursive routine to only that side of the sub-array.

T(n) = O(n) + T(n/2)

While this may be suggestive of O(nlogn), it is not. It reduces to 8cn which is in fact O(n).