Linear-Time Selection

During our discussion of quick-sort, we claimed in passing that we can find the median of an unsorted array in linear time. The first such algorithm was discovered by Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob Tarjan in the early 1970s. Their algorithm actually solves the more general problem of selecting the $k$th smallest element in an $n$-element array, given the array and the integer $k$ as input, using a variant of an algorithm called quickselect or one-armed quick-sort. Quick-select was first described by Tony Hoare in 1961, literally on the same page where he first published quick-sort.

Quickselect

The generic quickselect algorithm chooses a pivot element, partitions the array using the same $Partition$ subroutine as quick-sort, and then recursively searches only one of the two subarrays, specifically, the one that contains the $k$th smallest element of the original input array. The pseudocode for quickselect is shown below.