To find the maximum and 4th Maximum of an array what is the minimum number of comparisons needed? I assume I have to use an algorithm similar to MinMax and the solution found here:
Find the 2nd largest element in an array with minimum number of comparisons\
But I'm not sure how i would adapt the tournament style to this scenario.
Interesting question...
I think the trick is just to run the tournament a 2nd time, but with the largest and 2nd largest removed from the set (as determined by tournament #1).
Tournament #1: To find in (1) [The largest] and in (2) [The 2nd largest]
Tournament #2: With (1) and (2) removed from the set. To find in (3) [The largest] and in (4) [The 2nd largest]. These will be the 3rd and 4th largest (respectively) from the original set.
[Edit]: I had better attempt some maths for completeness.
(1) + (2) + (3) + (4)
=> (n - 1) + (log n - 1) + ((n - 2) - 1) + (log (n-2) - 1)
=> 2n + (log n) + (log (n-2)) - 6
=> 2n + log (n^2 - 2n) - 6