3

how do you setup minimum number of comparisons in general?

1

3 Answers 3

8

To cite Donald Knuth (by way of Wikipedia, since I don't have my copy of TAOCP at the moment), the lower bound for the number of comparisons is six:

http://en.wikipedia.org/wiki/Selection_algorithm (scroll down to the section entitled "Lower Bounds").

Your goal is, effectively, to find the k lowest values where k is half the size of the list, rounded up, (so, k = 3; n = 5) and then take the max of those. Plugging that into the formula there on the page, you get:

(5 - 3) + 1 + 1 + 2 = 6

In this case, the actual minimum number of required comparisons is also six.

If you're in doubt that the task of finding the median is as hard as finding k lowest values, you may refer to Knuth's TAoCP, volume 3, excercise #2 after 5.3.3 chapter.

4
  • However, it's not obvious that finding N/2 lowest elements would be as hard as finding only one median.
    – P Shved
    Commented Oct 18, 2009 at 19:42
  • Once you've found the N/2 smallest elements, the largest of those elements is the median, and since you've just done all of the necessary comparisons, you know which of the N/2 smallest elements is the largest. Commented Oct 18, 2009 at 20:05
  • Agreed. 6 is the best you can do .
    – DarthVader
    Commented Oct 19, 2009 at 2:05
  • Something is wrong with your or my calculation. (5 - 3) + 2 + 3 is my solution. log_2(4) = 2 and ceil(log_2(5) = 3. Need help! Commented Mar 10, 2013 at 21:50
4

There is a lot of material on this in volume 3 of Donald Knuth's The Art of Computer Programming, in section 5.3.3, Minimum-Comparison Selection, where the more general question of the minimum number of comparisons required to select the tth largest of n values is considered. (This value is denoted by Vt(n)).

Knuth gives an upper bound of n - t + (t-1)⌈lg(n + 2 - t)⌉ for Vt(n), achieved by first determining the largest element of n - t + 2 by a tournament system, removing this (since it cannot be the tth largest) and replacing it with one of the remaining elements, continuing this procedure until all elements have been a part of this procedure, and then the largest element at this stage is the tth largest of the original set. In this case, n = 5 and t = 3, so the upper bound given by this formula is 6 comparisons.

Knuth mentions that this upper bound is exact when n ≤ 6, so that applies in this case. In general, my understanding is that there are no general procedures for finding minimum-comparison algorithms for selection (and sorting), and records for increasing values of n typically use special tricks that either are not generally applicable to larger values or are simply beaten by other tricks when n increases.

1

Answer is 6. Here's how. (Originally posted on How do I calculate the "median of five" in C#?)

Let's denote these five numbers by a, b, c, d, and e.

Compare a and b, c and d. WLOG let a < b, c < d. (2 comparisons so far)

Compare a and c. WLOG let a < c. (3)

Compare b and e. (4) Note that b is used instead of d (and they cannot be swapped) because b is the "counterpart" of the smaller of a and c.

Case 1: let b < e.

____Compare b and c — the greater value is the median. (5)

Case 2: let b > e.

____Compare a and e. (5)

____Case 2.1: let a < e.

________Compare c and e — the greater value is the median. (6)

____Case 2.2: let a > e.

________Compare b and c — the smaller value is the median. (6)

(Formatting is ugly ik >.<)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.