Selection algorithm

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:

• Sort the collection
• If the output of the sorting algorithm is an array, retrieve its ${\displaystyle k}$th element; otherwise, scan the sorted sequence to find the ${\displaystyle k}$th element.

The time for this method is dominated by the sorting step, which requires ${\displaystyle \Theta (n\log n)}$ time using a comparison sort.[2][3] 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.[4] 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}$.[3]

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.[5] 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)}$.[6] 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}$.[7]

As with the related pivoting-based quicksort algorithm, the partition of the input into ${\displaystyle L}$ and ${\displaystyle R}$ may be done by making new collections for these sets, or by a method that partitions a given list or array data type in-place. Details vary depending on how the input collection is represented.[8] The time to compare the pivot against all the other values is ${\displaystyle O(n)}$.[7] However, pivoting methods differ in how they choose the pivot, which affects how big the subproblems in each recursive call will be. The efficiency of these methods depends greatly on the choice of the pivot. If the pivot is chosen badly, the running time of this method can be as slow as ${\displaystyle O(n^{2})}$.[4]

• If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a geometric series to ${\displaystyle O(n)}$. However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each call.[7]
• Quickselect chooses the pivot uniformly at random from the input values. It can be described as a prune and search algorithm,[9] a variant of quicksort, with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections ${\displaystyle L}$ and ${\displaystyle R}$, quickselect only makes one of these two calls. Its expected time is ${\displaystyle O(n)}$.[2][7][9] For any constant ${\displaystyle C}$, the probability that its number of comparisons exceeds ${\displaystyle Cn}$ is superexponentially small in ${\displaystyle C}$.[10]
• The Floyd–Rivest algorithm, a variation of quickselect, chooses a pivot by randomly sampling a subset of ${\displaystyle r}$ data values, for some sample size ${\displaystyle r}$, and then recursively selecting two elements somewhat above and below position ${\displaystyle rk/n}$ of the sample to use as pivots. With this choice, it is likely that ${\displaystyle k}$ is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is ${\displaystyle n+\min(k,n-k)+o(n)}$.[11] In their original work, Floyd and Rivest claimed that the ${\displaystyle o(n)}$ term could be made as small as ${\displaystyle O({\sqrt {n}})}$ by a recursive sampling scheme, but the correctness of their analysis has been questioned.[12][13] Instead, more rigorous analysis has shown that a version of their algorithm achieves ${\displaystyle O({\sqrt {n\log n}})}$ for this term.[14] Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a true random number generator, a version of the Floyd–Rivest algorithm using a pseudorandom number generator seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.[15]

Visualization of pivot selection for the median of medians method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the ${\displaystyle 3n/10}$ elements in the upper left quadrant will be less than the pivot, and the ${\displaystyle 3n/10}$ elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.

• The median of medians method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these ${\displaystyle n/5}$ medians. Using the resulting median of medians as the pivot produces a partition with ${\displaystyle \max(|L|,|R|)\leq 7n/10}$. Thus, a problem on ${\displaystyle n}$ elements is reduced to two recursive problems on ${\displaystyle n/5}$ elements (to find the pivot) and at most ${\displaystyle 7n/10}$ elements (after the pivot is used). The total size of these two recursive subproblems is at most ${\displaystyle 9n/10}$, allowing the total time to be analyzed as a geometric series adding to ${\displaystyle O(n)}$. Unlike quickselect, this algorithm is deterministic, not randomized.[2][4][5] It was the first linear-time deterministic selection algorithm known,[5] and is commonly taught in undergraduate algorithms classes as an example of a divide and conquer that does not divide into two equal subproblems.[2][4][9][16] However, the high constant factors in its ${\displaystyle O(n)}$ time bound make it slower than quickselect in practice,[3][9] and slower even than sorting for inputs of moderate size.[4]
• Hybrid algorithms such as introselect can be used to achieve the practical performance of quickselect with a fallback to medians of medians guaranteeing worst-case ${\displaystyle O(n)}$ time.[17]

The deterministic selection algorithms with the smallest known numbers of comparisons, for values of ${\displaystyle k}$ that are far from ${\displaystyle 1}$ or ${\displaystyle n}$, are based on the concept of factories, introduced in 1976 by Arnold Schönhage, Mike Paterson, and Nick Pippenger.[18] These are methods that build partial orders of certain specified types, on small subsets of input values, by using comparisons to combine smaller partial orders. As a very simple example, one type of factory can take as input a sequence of single-element partial orders, compare pairs of elements from these orders, and produce as output a sequence of two-element totally ordered sets. The elements used as the inputs to this factory could either be input values that have not been compared with anything yet, or "waste" values produced by other factories. The goal of a factory-based algorithm is to combine together different factories, with the outputs of some factories going to the inputs of others, in order to eventually obtain a partial order in which one element (the ${\displaystyle k}$th smallest) is larger than some ${\displaystyle k-1}$ other elements and smaller than another ${\displaystyle n-k}$ others. A careful design of these factories leads to an algorithm that, when applied to median-finding, uses at most ${\displaystyle 2.942n}$ comparisons. For other values of ${\displaystyle k}$, the number of comparisons is smaller.[19]

Parallel algorithms for selection have been studied since 1975, when Leslie Valiant introduced the parallel comparison tree model for analyzing these algorithms, and proved that in this model selection using a linear number of comparisons requires ${\displaystyle \Omega (\log \log n)}$ parallel steps, even for selecting the minimum or maximum.[20] Researchers later found parallel algorithms for selection in ${\displaystyle O(\log \log n)}$ steps, matching this bound.[21][22] In a randomized parallel comparison tree model it is possible to perform selection in a bounded number of steps and a linear number of comparisons.[23] On the more realistic parallel RAM model of computing, with exclusive read exclusive write memory access, selection can be performed in time ${\displaystyle O(\log n)}$ with ${\displaystyle O(n/\log n)}$ processors, which is optimal both in time and in the number of processors.[24] With concurrent memory access, slightly faster parallel time is possible in general,[25] and the ${\displaystyle \log n}$ term in the time bound can be replaced by ${\displaystyle \log k}$.[26]

When data is already organized into a data structure, it may be possible to perform selection in an amount of time that is sublinear in the number of values. As a simple case of this, for data already sorted into an array, selecting the ${\displaystyle k}$th element may be performed by a single array lookup, in constant time.[27] For values organized into a two-dimensional array of size ${\displaystyle m\times n}$, with sorted rows and columns, selection may be performed in time ${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$, or faster when ${\displaystyle k}$ is small relative to the array dimensions.[27][28] For a collection of ${\displaystyle m}$ one-dimensional sorted arrays, with ${\displaystyle k_{i}}$ items less than the selected item in the ${\displaystyle i}$th array, the time is ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$.[28]

Selection from data in a binary heap takes time ${\displaystyle O(k)}$. This is independent of the size ${\displaystyle n}$ of the heap, and faster than the ${\displaystyle O(k\log n)}$ time bound that would be obtained from best-first search.[28][29] This same method can be applied more generally to data organized as any kind of heap-ordered tree (a tree in which each node stores one value in which the parent of each non-root node has a smaller value than its child). This method of performing selection in a heap has been applied to problems of listing multiple solutions to combinatorial optimization problems, such as finding the k shortest paths in a weighted graph, by defining a state space of solutions in the form of an implicitly defined heap-ordered tree, and then applying this selection algorithm to this tree.[30] In the other direction, linear time selection algorithms have been used as a subroutine in a priority queue data structure related to the heap, improving the time for extracting its ${\displaystyle k}$th item from ${\displaystyle O(\log n)}$ to ${\displaystyle O(\log ^{*}n+\log k)}$; here ${\displaystyle \log ^{*}n}$ is the iterated logarithm.[31]

For a collection of data values undergoing dynamic insertions and deletions, the order statistic tree augments a self-balancing binary search tree structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the ${\displaystyle k}$th element in the current set to all be performed in ${\displaystyle O(\log n)}$ time per operation.[2] Going beyond the comparison model of computation, faster times per operation are possible for values that are small integers, on which binary arithmetic operations are allowed.[32] It is not possible for a streaming algorithm with memory sublinear in both ${\displaystyle n}$ and ${\displaystyle k}$ to solve selection queries exactly for dynamic data, but the count–min sketch can be used to solve selection queries approximately, by finding a value whose position in the ordering of the elements (if it were added to them) would be within ${\displaystyle \varepsilon n}$ steps of ${\displaystyle k}$, for a sketch whose size is within logarithmic factors of ${\displaystyle 1/\varepsilon }$.[33]