Selection algorithm: Difference between revisions

Revision as of 01:49, 31 March 2023

Revision as of 02:07, 31 March 2023

Line 51:

For deterministic algorithms, it has been shown that selecting the <math>k</math> element requires <math>\bigl(1+H(k/n)\bigr)n+\Omega(\sqrt n)</math> comparisons, where <math display=block>H(x)=x\log_2\frac1x + (1-x)\log_2\frac1{1-x}</math> is the [[binary entropy function]].{{r|benjoh}} The special case of median-finding has a slightly larger lower bound on the number of comparisons, at least <math>(2+\varepsilon)n</math>, for <math>\varepsilon\approx 2^{-80}</math>.{{r|dz01}}

== Exact numbers of comparisons ==

Knuth supplies the following triangle of numbers summarizing known pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The <math>n</math>th row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the <math>k</math>th number within each row gives the number of comparisons needed to select the <math>k</math>th smallest value from an input of that size. The rows are symmetric because selecting the <math>k</math>th smallest requires exactly the same number of comparisons, in the worst case, as selecting the <math>k</math>th largest.{{r|knuth}}

{{center|0}}

{{center|1 &nbsp;&nbsp; 1}}

{{center|2 &nbsp;&nbsp; 3 &nbsp;&nbsp; 2}}

{{center|3 &nbsp;&nbsp; 4 &nbsp;&nbsp; 4 &nbsp;&nbsp; 3}}

{{center|4 &nbsp;&nbsp; 6 &nbsp;&nbsp; 6 &nbsp;&nbsp; 6 &nbsp;&nbsp; 4}}

{{center|5 &nbsp;&nbsp; 7 &nbsp;&nbsp; 8 &nbsp;&nbsp; 8 &nbsp;&nbsp; 7 &nbsp;&nbsp; 5}}

{{center|6 &nbsp;&nbsp; 8 &nbsp; 10 &nbsp; 10 &nbsp; 10 &nbsp; 8 &nbsp;&nbsp; 6}}

{{center|7 &nbsp;&nbsp; 9 &nbsp; 11 &nbsp; 12 &nbsp; 12 &nbsp; 11 &nbsp; 9 &nbsp;&nbsp; 7}}

{{center|8 &nbsp; 11 &nbsp; 12 &nbsp; 14 &nbsp; 14 &nbsp; 14 &nbsp; 12 &nbsp; 11 &nbsp; 8}}

{{center|9 &nbsp; 12 &nbsp; 14 &nbsp; 15 &nbsp; 16 &nbsp; 16 &nbsp; 15 &nbsp; 14 &nbsp; 12 &nbsp; 9}}

== Language support ==