Team ordering You have the results of a completed roundrobin

Team ordering You have the results of a completed round-robin tournament in which n teams played each other once. Each game ended either with a victory for one of the teams or with a tie. Design an algorithm that lists the teams in a sequence so that every team did not lose the game with the team listed immediately after it. What is the time efciency class of your algorithm?

Solution

This problem can be solved using any of the best sorting techniques. Lets try to solve it using the devide and conquer technique.

The analogy is as follows:-

Each match between the teams would be one comparision against each other, as there could be a case of tie also which implies that the sorting would be of non decreasing( In which 1 means the best team and n means the worst team).

So converting the same problem into the number problem makes it easy to solve using Either the \"Quick Sort\" or the \"Merge Sort\".

We can use the Merge Sort fo the above case.

Merge Sort uses devide and conquer technique, In which it devide the group into two parts recursively and at n==2 , it compares the numbers, and expand the result.

suppose we have 7 teams

2 4 5 4 3 1 6

Now divide the above teams recursively:-

2 4 5 4 3 1 6

2 4 5 4 3 1 6

now as we have reached at the bas case (n==2), we will compare these numbers (have a match against each other)

2 4 4 5 1 3 6 (number of matches 1(2,4) + 1(5,4) + 1(3,1) = 3)

Now we merge the division.

1, 2 ,3, 4, 4, 5

The best time complexity of this algorithm would be NLogN where N being the number of teams.