In computer science, a selection algorithm is an algorithm for finding the ${\displaystyle k}$th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the ${\displaystyle k}$th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of ${\displaystyle n}$ values, these algorithms take linear time, ${\displaystyle O(n)}$ as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time ${\displaystyle O(1)}$.

An algorithm for the selection problem takes as input a collection of values, and a number ${\displaystyle k}$. It outputs the ${\displaystyle k}$th smallest of these values, or, in some versions of the problem, a collection of the ${\displaystyle k}$ smallest values. For this to be well-defined, it should be possible to sort the values into an order from smallest to largest; for instance, they may be integers, floating-point numbers, or some other kind of object with a numeric key. However, they are not assumed to have been already sorted. Often, selection algorithms are restricted to a comparison-based model of computation, as in comparison sort algorithms, where the algorithm has access to a comparison operation that can determine the relative ordering of any two values, but may not perform any other kind of arithmetic operations on these values.

To simplify the problem, some works on this problem assume that the values are all distinct from each other, or that some consistent tie-breaking method has been used to assign an ordering to pairs of items with the same value as each other. Another variation in the problem definition concerns the numbering of the ordered values: is the smallest value obtained by setting ${\displaystyle k=0}$, as in zero-based numbering of arrays, or is it obtained by setting ${\displaystyle k=1}$, following the usual English-language conventions for the smallest, second-smallest, etc.? This article follows the conventions used by Cormen et al., according to which all values are distinct and the minimum value is obtained from ${\displaystyle k=1}$.

With these conventions, the maximum value, among a collection of ${\displaystyle n}$ values, is obtained by setting ${\displaystyle k=n}$. When ${\displaystyle n}$ is an odd number, the median of the collection is obtained by setting ${\displaystyle k=(n+1)/2}$. When ${\displaystyle n}$ is even, there are two choices for the median, obtained by rounding this choice of ${\displaystyle k}$ down or up, respectively: the lower median with ${\displaystyle k=n/2}$ and the upper median with ${\displaystyle k=n/2+1}$.

As a baseline algorithm, selection of the ${\displaystyle k}$th smallest value in a collection of values can be performed by the following two steps:

The time for this method is dominated by the sorting step, which requires ${\displaystyle \Theta (n\log n)}$ time using a comparison sort. Even when integer sorting algorithms may be used, these are generally slower than the linear time that may be achieved using specialized selection algorithms. Nevertheless, the simplicity of this approach makes it attractive, especially when a highly-optimized sorting routine is provided as part of a runtime library, but a selection algorithm is not. For inputs of moderate size, sorting can be faster than non-random selection algorithms, because of the smaller constant factors in its running time. This method also produces a sorted version of the collection, which may be useful for other later computations, and in particular for selection with other choices of ${\displaystyle k}$.

For a sorting algorithm that generates one item at a time, such as selection sort, the scan can be done in tandem with the sort, and the sort can be terminated once the ${\displaystyle k}$th element has been found. One possible design of a consolation bracket in a single-elimination tournament, in which the teams who lost to the eventual winner play another mini-tournament to determine second place, can be seen as an instance of this method. Applying this optimization to heapsort produces the heapselect algorithm, which can select the ${\displaystyle k}$th smallest value in time ${\displaystyle O(n+k\log n)}$. This is fast when ${\displaystyle k}$ is small relative to ${\displaystyle n}$, but degenerates to ${\displaystyle O(n\log n)}$ for larger values of ${\displaystyle k}$, such as the choice ${\displaystyle k=n/2}$ used for median finding.

Many methods for selection are based on choosing a special "pivot" element from the input, and using comparisons with this element to divide the remaining ${\displaystyle n-1}$ input values into two subsets: the set ${\displaystyle L}$ of elements less than the pivot, and the set ${\displaystyle R}$ of elements greater than the pivot. The algorithm can then determine where the ${\displaystyle k}$th smallest value is to be found, based on a comparison of ${\displaystyle k}$ with the sizes of these sets. In particular, if ${\displaystyle k\leq |L|}$, the ${\displaystyle k}$th smallest value is in ${\displaystyle L}$, and can be found recursively by applying the same selection algorithm to ${\displaystyle L}$. If ${\displaystyle k=|L|+1}$, then the ${\displaystyle k}$th smallest value is the pivot, and it can be returned immediately. In the remaining case, the ${\displaystyle k}$th smallest value is in ${\displaystyle R}$, and more specifically it is the element in position ${\displaystyle k-|L|-1}$ of ${\displaystyle R}$. It can be found by applying a selection algorithm recursively, seeking the value in this position in ${\displaystyle R}$.