Talk:Tournament sort

Algorithm

The definition from the 1998 version of the OpenVME manual 'Programming Utilities', Chapter 3 'Sorting and Merging':

"[the tournament technique] means that all the records to be sorted are split into pairs and each pair is compared according to the key specification given for the overall sorting process. The survivor from each comparison plus any unpaired record then goes forward to the next stage when they are again paired and compared. This process is repeated until only one survivor remains and then this record is output.

The remaining records are again paired and compared through several stages of the process until another lone survivor is found and output.

This process continues until all the records have been output.

If there are n records to be sorted the first output record is found after n -1 comparisons and each subsequent record in an average log2n comparisons.

In logical terms, the survivor of a comparison is the record that would be output first in the sorting process according to the key specification given for the overall process. In real terms, only the loser of each comparison is saved in store and the winner is sent forward to the next stage. This means that the amount of storage needed for the sorting process is greatly reduced since no record references are unnecessarily duplicated in store."

This is the only definition I've found, and it doesn't make enough sense to create a usable program from. Starfiend (talk) 00:16, 16 November 2009 (UTC)

I agree. Making a diagram yields some insight. An adequate diagram is found at wikipedia/Playoff_format 25% down the page. If we were sorting these, after 3 rounds Iraq is determined best and placed first in the output list. Then Iraq is removed from the entire chart; this leaves S.Arabia, S.Korea, and Vietnam unsorted, so new games are arranged to sort these and the winner is placed in the output list after Iraq. The process repeats until everybody's sorted. But how exactly this is to be done, or what they mean by "saved in store" I would have to speculate blindly. Do they really expect the winners of the first round of games to magically continue to exist if they don't store them? Friendly Person (talk) 00:22, 5 May 2011 (UTC)

As I've understood it, a binary tree is used to store the tournament with the initial records as the leaves and the resulting matches as the inner nodes. For the match results they only store the loser as all subsequent operation will be to replace the ultimate winner of the tournament which has to be the winner of all affected records.

I can try to sketch up some pseudocode to illustrate how I think. I'll show it here when it's done.

81.231.83.135 (talk) 22:58, 15 June 2011 (UTC)

Here is an attempt at some pseudocode to explain how it works. It will need editing if it is to be used in the article itself. 81.231.83.135 (talk) 04:29, 16 June 2011 (UTC)

procedure TournamentSort(List records)
    List contestants := records
    List matches := {}
    
    while length(contestants) > 1 # Loops rounds until we're left with a single victor
        List winners := {}
        List previous_matches := matches
        matches := {}
        
        while length(contestants) >= 2 # Pairs up matches
            # Take two first contestants and calculate winner and loser.
            winners.add(winner)
            # Create matchrecord from contestants' previous matchrecords.
            matchrecord.loser := loser
            matches.add(matchrecord)
        end while
        
        if length(contestants) > 0 # Advance unpaired contestant.
            winners.add(contestants.pop())
            matches.add(previous_matches.pop())
        end if
        
        contestants := winners
    end while
    
    winner := contestants.pop() # Last standing is the winner
    
    List sorted_list := {}
    while length(sorted_list) < length(records) # Loops until all elements are sorted
        sorted_list.add(winner)
        # Set match to be the first match the winner was in (which I forgot to put in this code)
        winner := match.loser
        # Fix eventual references for current and previous matches
        
        while (match.next_match exists) # Goes through all the records the old winner was in
            match := match.next_match
            # Swap winner and match.loser if needed
        end while
    end while
    
    return sorted_list
end procedure

more references

Martin A. Goetz: Internal and tape sorting using the replacement-selection technique. 201-206 -- see https://dblp.org/db/journals/cacm/cacm6.html -- this is the original source of tree-of-losers priority queues and their use in sorting Goetz Graefe: Priority queues for database query processing. BTW 2023: 27-46 -- from https://dblp.org/db/conf/btw/btw2023.html -- some auxiliary material and source code for tree-of-losers operations 2600:1700:B270:8DE0:ED30:6EEA:F32B:A85 (talk) 22:42, 16 April 2024 (UTC)