Expected Time Bounds for Selection

A new selection algorithm is presented which
is shown to be very efficient on the average, 
both theoretically and practically.  The number of comparisons
used to select the ith smallest of n numbers 
is n+min(i,n-i)+o(n).  A lower bound within 9
percent of the above formula is also derived.

CACM March, 1975

Floyd, R. W.
Rivest, R. L.

selection, computational complexity, medians, tournaments, quantiles

5.30 5.39

CA750304 JB January 9, 1978  4:52 PM

1919	4	2784
2191	4	2784
2388	4	2784
2783	4	2784
2784	4	2784
2784	4	2784
2784	4	2784
3054	4	2784
3121	4	2784
864	4	2784
1729	5	2784
309	5	2784
2783	5	2784
2784	5	2784
2784	5	2784
2784	5	2784
2837	5	2784
2784	6	2784
2842	6	2784