how do you setup minimum number of comparisons in general?
views:
553answers:
2
+5
A:
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%5Falgorithm (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.
James McNellis
2009-10-18 19:22:28
However, it's not obvious that finding N/2 lowest elements would be as hard as finding only one median.
Pavel Shved
2009-10-18 19:42:03
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
2009-10-18 20:05:13
Thanks for the TAoCP reference, Pavel.
James McNellis
2009-10-18 20:34:56
Agreed. 6 is the best you can do .
2009-10-19 02:05:48