A friend of mine recently gave me the following problem:
Given an unsorted set of numbers find the minimum and maximum of set in a maximum of $1.5n$ comparisons.
My answer involves splitting the list up pairwise and finding the result on the only half of the set.
- Go through list and compare every even index to its immediate right (odd) index. Sort each pair numerically within itself. This step takes $\dfrac{1}{2}n$ comparisons.
- Find the minimum of every odd index and find the maximum of every even element using the typical algorithm. This step takes $n$ comparisons.
Note that this could be done in one pass by doing the pair comparison and the min/max comparison in one pass.
Is there a better way?
Funny trick. :-)
ReplyDeleteYou could also decide to use groups bigger than size two. This still seems to be profitable up to groups of size 5, compared to the naïve approach that requires 2n comparisons:
http://www.wolframalpha.com/input/?i=%282+%2B+ceil%28log2%28x%21%29%29%29%2Fx