sorting tournament seeds
The ideas of matching players from the top and bottom is correct but not quite complete. Doing it once works great for the first round:
while (seeds.length)
{
firstRound.push(seeds.shift());
firstRound.push(seeds.pop());
}
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5
...but in the second round, seed 1 meets seed 2 and 3 meets 4. We need to do the first/last shuffle for each round. First time through, we move each element individually. Second time through, we move each PAIR of elements. Third time through we move groups of four, etc, until our group size is seeds.length/2
. Like so:
// this is ruby, aka javascript psuedo-code :)
bracket_list = seeds.clone
slice = 1
while slice < bracket_list.length/2
temp = bracket_list
bracket_list = []
while temp.length > 0
bracket_list.concat temp.slice!(0, slice) # n from the beginning
bracket_list.concat temp.slice!(-slice, slice) # n from the end
end
slice *= 2
end
return bracket_list
Here's what the array will look like as you go through the iterations (parenthesis indicate the increasing group size):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
(1, 16), (2, 15), (3, 14), (4, 13), (5, 12), (6, 11), (7, 10), (8, 9)
(1, 16, 8, 9), (2, 15, 7, 10), (3, 14, 6, 11), (4, 13, 5, 12)
(1, 16, 8, 9, 4, 13, 5, 12), (2, 15, 7, 10, 3, 14, 6, 11)
So now, after the bottom 8 players are eliminated, we're left with 1, 8, 4, 5, 2, 7, 3, 6
. After the bottom 4 are eliminated from there we have 1, 4, 2, 3
, and in the final round just 1, 2
.
It's hard to explain this without being able to draw a bracket... Let me know if I can clarify something for you.
This is probably not as efficient as @alex's answer using a custom sort
function, but certainly easier to write and understand:
// This algorithm assumes that seeds.length is an even number
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
firstRound = [];
while (seeds.length)
{
firstRound.push(seeds.shift());
firstRound.push(seeds.pop());
}
// seeds is now empty
// firstRound is now [1, 8, 2, 7, 3, 6, 4, 5]
Demo 1
Actually, I just thought of a faster algorithm (in-place "sorting", takes O(n)
time):
// Also assumes that seeds.length is an even number
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
numSeeds = seeds.length,
stop = numSeeds >> 1,
temp;
for (var i=1; i<stop; i=i+2)
{
temp = seeds[i];
seeds[i] = seeds[numSeeds-i];
seeds[numSeeds-i] = temp;
}
// seeds is now [1, 8, 3, 6, 5, 4, 7, 2]
Demo 2
Note that neither of these algorithms generates exactly the same order of pairs as in the OP, but they both generate the same set of pairs:
(1,8)
(2,7)
(3,6)
(4,5)
I've come up with a solution, but it's outside the scope of just "sorting arrays".
The (javascript) code is at http://jsbin.com/ukomo5/2/edit.
In basic terms, the algorithm assumes that no upsets will occur in the bracket, therefore seeds 1 and 2 should meet in the final round. It iterates through each seed in each round (starting from the pre-calculated grand final, working backwards), calculating the unknown seed in the match in the previous round that the current seed (in the iteration) had won. This can be done because given a seed and round number, you can work out what the other seed should be:
other seed = number of seeds in round + 1 - the known seed
To illustrate, in the semifinals:
Semifinal 1 (where known seed is 1): other seed = 4 + 1 - 1 = 4
Semifinal 2 (where known seed is 2): other seed = 4 + 1 - 2 = 3
I just noticed this pattern when looking at a "no upsets" bracket I had drawn.
In the final iteration (ie round 1) all seeds and their position are known, ready to be assigned to matches. The correct sorted array is below:
1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11
Thanks again to Matt Ball who came up with a correct solution for small brackets (It's difficult to state the problem and desired solution without detailed context, which I didn't do completely in my initial question).
If anyone has another solution or a more elegant version of my solution let us know!