Quickselect is an algorithm for finding the element of a specified rank in an unordered collection—for example, the smallest element, the median, or the tenth-largest element—without fully sorting the collection. It solves the selection problem by repeatedly partitioning elements around a chosen pivot and continuing only in the partition that contains the desired rank. With uniformly randomized pivot selection and suitable handling of equal values, its expected running time is linear in the number of elements, although its worst-case running time is quadratic. Quickselect is closely related to quicksort, but processes only one side of each partition rather than sorting both sides.
Selection and order statistics
The element occupying a given position in sorted order is called an order statistic. Using zero-based indexing, the selection problem takes a collection of elements and an index , where , and returns the value that would occupy position if the collection were sorted.
For example, given
[9, 1, 8, 2, 7, 3, 6, 4, 5]
the element at zero-based rank is , the median. Finding that value does not require determining the complete sorted order of the remaining elements.
Ranks count occurrences, not just distinct values. In the sorted collection [2, 2, 5, 8], both ranks and contain . An implementation may return the selected value, an object with that value, or an iterator or index identifying its position.
Unlike a sorting algorithm, Quickselect generally leaves most of the collection unordered. An in-place version can nevertheless establish that elements before the selected position are no greater than the selected value and elements after it are no smaller.
Partitioning principle
Quickselect maintains an active range containing the desired element. Each iteration performs three operations:
- Choose a pivot from the active range.
- Partition the range according to comparisons with the pivot.
- Either return the result or continue within the part containing the target rank.
A three-way partition divides the range into elements less than the pivot, elements equivalent to the pivot, and elements greater than the pivot. If the target position falls in the equal region, selection is complete. Otherwise, only the appropriate outer region remains relevant.
This resembles divide and conquer, but because only one subproblem is pursued, Quickselect is also described as a prune-and-search or decrease-and-conquer algorithm.
Pseudocode
The following pseudocode uses inclusive range bounds and an absolute, zero-based target index:
quickselect(A, k):
require 0 <= k < length(A)
left = 0
right = length(A) - 1
while left < right:
p = uniformly random integer from left through right
pivot = value of A[p]
(lt, gt) = partition_three_way(A, left, right, pivot)
# A[left .. lt-1] contains values < pivot
# A[lt .. gt] contains values equivalent to pivot
# A[gt+1 .. right] contains values > pivot
if k < lt:
right = lt - 1
else if k > gt:
left = gt + 1
else:
return A[k]
return A[left]
Here, partition_three_way rearranges the active range in place and returns the boundaries of its equal region. The pivot value must remain available during partitioning even if its original array position is overwritten.
Correctness follows from the partition ordering: every element in the less-than region precedes every element in the equal region in sorted order, and every element in the greater-than region follows it. Consequently, the target rank cannot belong to a discarded region.
Partition conventions
Not all partition routines have the same contract. Some place a pivot element at its final sorted position; others return a boundary separating two regions without placing any particular element at its final rank. A Quickselect implementation must use update rules appropriate to its partition routine.
Three-way partitioning is particularly useful when values repeat. A two-way partition that consistently places all equal values on one side can make almost no progress on an all-equal input. Three-way partitioning resolves that input in a single linear pass.
Complexity
The principal time complexity bounds for ordinary Quickselect are:
| Case | Running time |
|---|---|
| Best case | |
| Expected, with uniform random pivots | |
| Worst case |
These bounds assume constant-time comparisons and element moves, and a partition procedure that scans the active range in linear time.
Expected linear time
If each pivot divides the active range reasonably evenly, the amount of partitioning work forms a geometric series. For example, repeatedly retaining about half the elements gives
Uniformly random pivots do not guarantee balanced partitions at every step. Nevertheless, a pivot falls within the middle half of the rank order with probability approximately one-half. Such a pivot leaves at most about three-quarters of the elements in whichever side must be searched. The expected number of partition steps needed to obtain such a reduction is bounded by a constant, yielding linear expected total work.
This expectation is over the algorithm’s random pivot choices and does not require a random input order. Randomized Quickselect is therefore a randomized algorithm that always returns a correct result but has variable running time, often classified as a Las Vegas algorithm.
Quadratic worst case
If each pivot is an extreme element and the desired rank remains in the larger partition, successive active ranges can have sizes . The work is then
A fixed rule such as always choosing the first element can produce this behavior on suitably ordered input. Randomization makes a consistently bad sequence unlikely, but does not eliminate the quadratic worst case.
Space usage
An iterative implementation with in-place partitioning uses auxiliary space. A recursive implementation also consumes call stack space: with randomized pivots, the expected recursion depth is , while the worst-case depth is .
Implementations that construct new collections for the partition regions have different allocation and memory costs; constant auxiliary space is a property of the in-place implementation, not of every formulation.
Pivot selection and related algorithms
Pivot choice strongly affects practical performance.
- Fixed-position pivots are inexpensive but can behave poorly on structured input.
- Uniform random pivots provide expected linear time for every fixed input.
- Median-of-three and other small samples often improve partition balance in practice, but do not alone guarantee a linear worst case.
- Larger or rank-aware samples can improve selection efficiency, at the cost of additional sampling work.
Median of medians
The median-of-medians algorithm provides a deterministic pivot strategy that guarantees linear worst-case selection time. In its standard form, elements are grouped into groups of five, the median of each group is found, and the median of those medians is selected recursively.
The resulting pivot guarantees that a constant fraction of elements can be discarded. Its running time satisfies a bound of the form
which yields . This stronger guarantee generally involves more pivot-selection work than simple randomized Quickselect.
Introselect
Introselect combines a fast Quickselect-style procedure with a fallback strategy when progress becomes inadequate. Its precise guarantees depend on both the trigger and the fallback. A linear-time fallback, combined with a bound on the work already spent, can provide worst-case linear selection. Merely imposing a recursion-depth limit does not by itself establish that bound.
Applications and limitations
Quickselect is useful when only a small part of the sorted order is required:
- Medians and sample quantiles: selection obtains the relevant ranked observations without sorting the entire sample. Quantile conventions involving interpolation may require two adjacent order statistics.
- Top- extraction: partitioning at the appropriate boundary isolates the smallest or largest elements. Sorting only that subset gives expected work of .
- Geometric data structures: median selection can divide points during construction of a balanced k-d tree.
- Data processing: rank-based cutoffs and trimming operations can use selection instead of full sorting.
An array or another mutable random-access sequence is the natural setting for in-place Quickselect. The method changes element order and is generally not stable: equal-key records need not retain their original relative order. Preserving the original arrangement may require a copy or an auxiliary array of indices.
Comparisons must define a consistent ordering. Floating-point NaN values require an explicit ordering policy because ordinary comparisons do not place them consistently among other values.
Quickselect also assumes repeated access to the active collection. For streaming data or collections too large for memory, a priority queue, an approximate quantile method, or an external-memory selection algorithm may be more appropriate. Repeatedly applying Quickselect independently for many ranks can duplicate partitioning work; shared multi-selection or full sorting may then be preferable.
History
Quickselect was introduced by C. A. R. Hoare in 1961 as Algorithm 65: Find. It developed alongside quicksort and uses the same central idea of partitioning around a pivot. The difference between recursively sorting both partitions and searching only the relevant partition accounts for the contrast between quicksort’s expected running time and Quickselect’s expected running time.