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 input, using a variant of an algorithm called quick-select (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.

Quick-select

The generic quick-select algorithm chooses a pivot element, partitions the array using the same PartitionPartition subroutine as QuickSortQuickSort, 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 quick-select 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