# finding best n players in minimum number of comparisons

I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 players?

I thought of using below approach to find out 2 best players.

So for finding out the 3rd best player we can use the same approach i.e. players lost again best best player + players lost against 2nd best player should be again played against each other to find out the 3rd best player.

Am I right if this would be the minimum number of comparisons to get 3rd best player?

Or should I divide the players in square root of input size and then play in groups as this?

Edit: When two players play better player always wins. You can design your own tournament strategy to figure out the best n players.

• en.wikipedia.org/wiki/Selection_algorithm
– D.W.
Nov 5 '17 at 18:00
• It's not clear what your model is. Are you assuming that the players have some linear order in skill, and when two players play, the better player always wins? Are we allowed to design the tournament (determine which players will play who, depending on who won the past games)? Are you looking to find the best 5 players, or only the 5 who performed the best in the tournament?
– D.W.
Nov 6 '17 at 6:41
• @D.W. When two players play better player always wins. Yes you can design the tournament. I am trying to find the best 5 players. Analogy: sorting the array and find the 5 largest/smallest number but with minimum number of comparisons. Nov 6 '17 at 17:38
• Can you edit your question to incorporate that information into the question, please? We want questions to be self-contained, so people don't have to read the comments to understand what you are asking. Thank you!
– D.W.
Nov 7 '17 at 4:14
• I still don't find it very clear what you mean by "design your own tournament". I'm pretty sure that you're using the word tournament in a non-technical sense (i.e. not a complete graph with each edge assigned a direction), but what makes this different to standard kth statistics? Apr 6 '18 at 12:59

You can't. There isn't enough information in a single elimination tournament to know who the $n$ best players are. All you can infer is who the best player is. You can't even tell who is second best; the second-best player could be any of the people who lost to the best player.

If you're not limited to a single-elimination tournament, I recommend you use a selection algorithm to find the top $n$ players, then use a sorting algorithm to rank-order those $n$ players. Asymptotically, this needs only $O(N + n \log n)$ matches if you start out with $N$ players and want to rank-order the top $n$ of them. If you only want to find the top $n$ players without rank-ordering them, a selection algorithm suffices, and then you'll only need $O(N)$ matches. You can study the literature on selection algorithms and sorting algorithms to figure out how to reduce the constant factor hidden in the big-O notation.

In practice if you want to hold some matches simultaneously, you might want parallelizable selection algorithms and sorting algorithms. Figuring out how to parallelize selection algorithms might be worth a question of its own.

Optimal to find best and second best is to build a binomial tree from the leaves up (i.e., compare disjoint pairs, compare the winners of pairs, and work your way up to the overall winner, always making sure to compare winners of groups of the same size). This ensures the second best is among those who lost to the winner, at most $$\lceil \log_2 n \rceil$$ elements. I'd repeat the above among the losers against the winner and second one, and repeat until you have all you want.

One easy way I can think of is

• Step1 : Sort the players wrt No.of matches won
• Step2 : Sort the players who have an equal No.of matches won wrt Best opponent faced

In the case given by you , if you sort wrt to "No. of matches won" you get a list in the following order

10,7,[6,9],[5,0,8,1] // After applying Step 1 to the list

Now you can see that the players in brackets have an equal "No. of matches won".So you need to sort the lists [6,9] and [5,0,8,1] wrt to the "Best opponent faced"

Start from the first list that appears from left

[6,9] becomes [9,6] because

• 9 faced 10 which comes first in the list obtained after Step 1.
• And 6 faced 7 which is second in the list obtained after Step 1

So

10,7,[6,9],[5,0,8,1] becomes

10,7,9,6,[5,0,8,1] //After applying Step 2 on [6,9]

Now if we sort [5,0,8,1] wrt to the "Best opponent faced" then we get [1,0,8,5] because

• 1 faced 10 which is first in the list

• 0 faced 7 which is second in the list

• 8 faced 9 which is third in the list

• and lastly 5 faced 6 which is fourth in the list

So 10,7,9,6,[5,0,8,1] becomes

10,7,9,6,1,0,8,5 //After applying Step 2 on [5,0,8,1].

You can repeatedly perform Step 2 unless you get the desired number of top players.Your top 5 players for the case in order are

10,7,9,6,1

Usually another performance criteria(like points scored) for sorting in Step 2 is available but I think this one suits if you don't have one.

• You list a proposed scheme but no justification for its correctness. I don't think it is correct. In particular, I don't think this is guaranteed to give you the 5 best players. Depending upon the design of who plays who, the 5 people who won the most games aren't necessarily the 5 best players.
– D.W.
Nov 5 '17 at 21:34
• @D.W. I mentioned that he needs another performance criterion for Step 2.He is trying to rank the players according to their wins or loss in the tournament.I guess the goal is not to find the best player but to find the best performance in terms of winning and losing in the tournament.I agree that I didn't present any justification for its correctness. Nov 5 '17 at 21:43
• @D.W Apparently I am taking the toughness/performance of the opponents for comparison between players on the same level who don't get to face each other Nov 5 '17 at 21:49
• @RomanticElectron I have clarified with more comments. Nov 6 '17 at 17:39
• @nomanpouigt I think my strategy will give you what you desire in $O(n)$. Nov 7 '17 at 12:45