Number of Comparisons finding the median of 7 numbers [closed]

Question

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

Hustler

I'd like to see your implementation - I can't seem to do it in fewer than 18 operations. – Weissmann

For a,b,c,d,e,f,g, try a<b,c<d, then make a<b, c<d;try b<d and let the winner compare with e, then eliminate the winner. Replace the winner with new key. In the worst case, I need another 3 comparisons to eliminate another key. Do it twice, then choose the largest in the last 4 keys. Is that clear? – Hustler

Answer 1

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.

Jena

It seems TAoCP is necessary. @-@ – Hustler

@zerr, No doubt, It is always necessary – Plenteous

Answer 2

If you allow comparisons in parallel (a modern CPU will probably do this for you), you can use a sorting network to solve the problem in six steps.

Flyn

Could you provide a reference to the 6 comparisons implementation? Thanks – Plenteous

Sure, here you go: angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Flyn

I saw that article but I think it doecan't says that n=7 could be done with 6 comparisons. – Plenteous

My apologies, try this: jgamble.ripco.net/cgi-bin/… -- note that I didn't say six comparisons, I said six steps (i.e., you have to perform some comparisons in parallel in a sorting network). – Flyn

Answer 3

For (7s) you know you're on the right track when you spot the flying robots (Hasse Diagram). There are two main cases to verify for 10 comps; other cases are not close to the limit. (7s) is close to a perfect puzzle, like E's Zebra Puzzle. Not too hard, but hard enough so only the disciplined will crack it on their first go.

Now (4s, 3), also with 7 numbers, is the equal of (7s). Here we assume that one of the numbers repeats three times (has multiplicity 3). I won't tell you what the answer (height of the optimal ternary dec. tree) is. Go find it fellas!

Remembrancer