# 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 $k$-th smallest element in an $n$-element array, given the array and the integer $k$ 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.

## Quick-select

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.

Create a free account to access the full course.

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