Search code examples
algorithmcomparemedianminimum

Number of Comparisons finding the median of 7 numbers

I can find the median with 12 comparisons. But I want to know the minimum number of comparisons and how to do it.

Solution

  • Donald Knuth has a chapter on "Minimum-Comparison Selection" in Volume III of The Art of Computer Programming.

    Knuth says, "no general method [of selection in the minimum number of comparisons] is evident as yet" but he gives some general methods that come close to the minimum.

    Looking at Table 5.3.3–1, we can see that V₄(7) = 10 (that is, you can find the 4th largest of 7 items using at most 10 comparisons), and the algorithm ("found manually by trial and error") is given in the solution to exercise 5.3.3–10.