how do you setup minimum number of comparisons in general?
Asked
Active
Viewed 1.4k times
3 Answers
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.
P Shved
- 96,026
- 17
- 121
- 165
James McNellis
- 348,265
- 75
- 913
- 977
-
However, it's not obvious that finding N/2 lowest elements would be as hard as finding only one median. – P Shved Oct 18 '09 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. – James McNellis Oct 18 '09 at 20: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! – user1091344 Mar 10 '13 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.
JaakkoK
- 8,247
- 2
- 32
- 50
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 >.<)
Yongqing Yu
- 11
- 2