Search code examples
algorithmsortingcomparisontournament

Finding the 3rd largest element in array of size (2^k +1) in n+2k-3 comparisons

"Find the 3rd largest element in array of size (2^k +1) in n+2k-3 comparisons."

This was a question I had in an Algorithms course final exam, which I didn't get all the points for. I'm stil not sure what is the correct answer after a thorough internet search.

I realize it is an extended version of the same problem with the second largest, but the tight comparison bound that was requested made the question to be tricky. I also found a mathematical explanation to find the K-th element here, however it was too complicated for me to understand.

Denote the array size to n = 2^k + 1.

In the exam itself my answer was something like this:

We'll use a tournament tree. First, we leave out an arbitrary element.
Then build the tree which will consist of 2^k elements. Therefore there are K levels in the tree (log(2^k)).

Finding the winner will take us n-2 comparisons.

Find the largest element among the ones who lost to the winner. (K-1 comp.)

Find the largest element among the ones who lost to the loser of the final. (K-2 comp.)

We'll compare these and the one we left out in the beginning. (2 comp.)

The largest of the 3 is the 3rd largest of the array.

Total comparisons: n - 2 + k - 1 + k - 2 + 2 = n + 2k - 3.

I got 10 points out of 25.

I've done 2 mistakes. The major one is if the desired element is in the winner's sub-tree, my answer will be incorrect. Also, the correct answer is supposed to be the second largest of the 3 I finally compared in the end.

Another algorithm I found is as follows:
-Building a tournament tree and finding the winner (n - 2)
-Finding the second largest by comparing all the losers to the winner. (also by a tournament tree) (k - 1)
-The answer lies among the largest of the losers to the second largest, and the losers to the one who lost in the final in the first tree. (log(k+1) + K-1-1)

-This solution assumes that the element we left out is not the largest in the array. If it is, I'm not sure how it acts. Also, I probably didn't understand the number of comparisons correctly.

I'll be happy to find out if there is a better explained algorithm. I will also be keen to know if there is more a generalized one for L-th largest (K was taken..).

Thanks in advance, Itay

Solution

    1. Construct a tournament tree on n - 1 = 2k of the elements, chosen arbitrarily. (n - 2 comparisons)

    2. At the leaf, replace the maximum of the chosen elements by the element not chosen. Rebuild the tournament tree. (k comparisons)

    3. Take the maximum of the elements that lost to the new maximum, as in the algorithm for second largest. (k - 1 comparisons)

    I'll leave the correctness proof as an exercise.