Average Case Selection

We consider problems such as selecting the k -th smallest of n numbers in as few comparisons as possible on average. n + k - 0(1) comparisons are proved to be necessary for this particular problem when k ≤ n /2. This shows a technique of Floyd and Rivest is essentially optimal. 7 n /4 = o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9 n /4 + o(n) and a lower bound of 2 n − o(n) are shown for the max-min-median problem.

Authors

• Walter Cunto
• J. Ian Munro

Keywords

No keywords are indexed for this paper.