Find 3rd largest number out of 7 under at most 11 comparisons

Question

I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?

Answer 1

Let $V_t(n)$ be the minimum number (in the worst case) of comparisons needed to find the $t$th largest of $n$ distinct values (selection algorithms).

Knuth (AOCP 5.3.3) describes a good method to find the required entry, the constructive basis for an upper bound (11), Hadian and Sobel's theorem:

$$ V_t(n) \leq n - t + (t-1) \lceil \lg(n+2-t) \rceil $$

In the immediate case this gives $V_3(7) \leq 4+2\lceil \lg 6 \rceil = 10 $, which is within the limit prescribed in this Question's title.

The general method is to set up a binary tree "knockout tournament" on $n-t+2$ of the entries, keeping $t-2$ of them in reserve. This requires $n-t+1$ comparisons, and produces a "winner" which exceeds (at least) $n-t+1$ of all the other entries. Since the $t$th largest entry exceeds only $n-t$ entries, it cannot be that winner. Replace the winner at the base (not the top) of the binary tree/tournament with one of the reserve entries, and recompare. Since this affects only one path (from base to top) in the tournament, this requires at most $\lceil \lg(n+2-t) \rceil$ added comparisons. Repeating this for each reserve entry, $t-2$ times in all, we are down to a set of $n-t+2$ entries whose current winner is also not the entry we want. Finally, replace that last winner with an entry that a priori loses every comparison, and again recompare (affecting only one path in the tree), which takes at most $\lceil \lg(n+2-t) \rceil - 1$ comparisions (taking advantage of the sure loser not to actually do a comparison). The $t$th largest entry comes out on top, in total using at most the number of comparisons given in the right hand side of the above inequality.

For the specific case $n=7$ and $t=3$, our initial knockout tournament would involve six of the entries, holding just one entry R in reserve. This uses five comparisons * to determine an initial winner X, which could have come from anywhere in the tree's base:

                               X
                               *
                              / \
                             /   \
                            *     \
                           / \     \
                          /   \     \
                         *     *     *
                        / \   / \   / \        |
                       ?   X ?   ? ?   ?       R

The depth of the binary tree is three, so recomparing after replacing the initial winner X with the reserve entry R results in at most three new comparisons # to find our second winner Y:

                               Y
                               #
                              / \
                             /   \
                            #     \
                           / \     \
                          /   \     \
                         #     *     *
                        / \   / \   / \
                       ?   R ?   ? ?   ? 

Finally, after putting a sure loser in place of second winner Y, recomparing produces the 3rd largest entry Z. This takes at most two new comparisons because the first comparison that Y took to the top of the tree is "skipped" by the sure loser. In total:

$$ V_3(7) \leq 5 + 3 + 2 = 10 $$

This turns out to be the sharp minimum number of comparisons possible in the worst case, as $V_3(7) = V_4(7) = V_5(7) = 10$ (see Knuth's AOCP, Vol. 3 Sorting and Searching, in Table I of Sec. 5.3.3, or the expanded table here by Ken Okansen).

---

• Hadian, Abdollah and Milton Sobel "Selecting the t-th largest using binary errorless comparisons," Technical Report 121, Dept. of Statistics, Univ. of Minnesota, May 1969 (15 pp.)