Tournament sort

Tournament sort

Tournament sort is a comparison sort algorithm. This method of sorting is quite efficientvague but requires memory of past comparisons. It involves several rounds of comparisons, much like a tournament among teams or players.

Let’s assume that there are 32 keys to be sorted. In the first round, each key is compared with one other. In each subsequent round, the larger keys from the previous round are compared with one of the other larger keys. This continues until one key is determined to be the largest. If there are N keys (32), there will have been N-1 (31) comparisons so far to eliminate all the elements except the “winner.” Also, the largest key must have been in lgN (5) comparisons.

To determine the second largest key, note that it must be one of the keys that was “beaten” by the largest key. There are only five such keys. The largest of these is found by comparing the first key eliminated with the second key eliminated, and the larger of these is compared with the third key eliminated, etc. Similarly, the third largest is among the keys beaten by the first or second largest, some of which may have already been compared with each other. In each round, there are fewer and fewer comparisons to be made, the maximum number of comparisons being lgN. This is true provided that the keys that have been compared the fewest numbers of times thus far are compared in subsequent rounds before keys that have had more comparisons. For example, when comparing for the second largest key, the key beaten by the largest key in the first round is compared to the key beaten by the largest key in round 2 before the key beaten in the last round is compared to anything.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Unreal Tournament — Pour les articles homonymes, voir UT. Unreal Tournament Éditeur …   Wikipédia en Français

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia

  • UAAP Season 71 men's basketball tournament — Infobox PhilCollFinals title=UAAP Season 71 Men s Basketball tagline= Madrama higherseed = UAAPteam|Ateneo lowerseed = UAAPteam|La Salle higherseed game1 = 69 higherseed game2 = 62 higherseed series = 2 lowerseed game1 = 61| lowerseed game2 = 51… …   Wikipedia

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”