This page gives algorithms for finding the `i'th largest of `n' elements with the fewest possible comparisons.
The problem has been widely studied in literature. Knuth gives a brief history of the problem and some known upper and lower bounds. Optimal algoritms are known for any `n' when `i' is one or two, but for example for finding the median (i = n/2), there is a significant performance gap from the best known algorithm (approximately 2.97 n + o(n) comparisons) to the tightest known minimum (2 n - o(n)).
Many other special cases are also known, such as the ones given in the table below. Many of these were previously found by Gasarch, Kelly and Pugh who introduced computer searching to find the optimal selection algorithms. The additional results presented in the table above have been found by my independent implementation, but it probably shares many characteristics with Gasarch's.
Numbers marked with one asterisk are new lower bounds. Numbers marked with two asterisks improve previously known algorithms. Since I found no previous studies of `V(14,3)' and `V(15,3)' in the literature, I have marked it with a question mark.
Click the number to get the optimal selection algorithm. If an optimal algorithm is not known, I've given the tightest known lower bound and the best known algorithm.
| V(n,i) | i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | i = 6 | i = 7 | i = 8 |
|---|---|---|---|---|---|---|---|---|
| n = 2 | 1 | |||||||
| n = 3 | 2 | 3 | ||||||
| n = 4 | 3 | 4 | ||||||
| n = 5 | 4 | 6 | 6 | |||||
| n = 6 | 5 | 7 | 8 | |||||
| n = 7 | 6 | 8 | 10 | 10 | ||||
| n = 8 | 7 | 9 | 11 | 12 | ||||
| n = 9 | 8 | 11 | 12 | 14 | 14 | |||
| n = 10 | 9 | 12 | 14 | 15 | 16 | |||
| n = 11 | 10 | 13 | 15 | 17 | 18* | 18** | ||
| n = 12 | 11 | 14 | 17 | 18** | 19** | 20** | ||
| n = 13 | 12 | 15 | 18* | 20* | 21** | 22** | 23* | |
| n = 14 | 13 | 16 | 19? | 21* | 23* | 24** | 24*..25** | |
| n = 15 | 14 | 17 | 20? | 23* | 25* | 25*..26 | 23..28 | 24..28 |
The search problem is considerably difficult and the tightest known lower bounds obtained by mathematical means soon exceed what is attainable by even rather intelligent search.