Linear-Time Selection

Understand the efficiency and effectiveness of the linear-time selection algorithm.

We'll cover the following

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 kk-th smallest element in an nn-element array, given the array and the integer kk as inputs, by using a variant of an algorithm called quickselect or one-armed quick-sort. Quickselect was first described by Tony Hoare in 1961, literally on the same page where he first published quick-sort.


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 kk-th smallest element of the original input array. The pseudocode for quickselect is shown below.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy