Talk:Tournament sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing / Software / CompSci (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
Taskforce icon
This article is supported by WikiProject Software (marked as Low-importance).
Taskforce icon
This article is supported by WikiProject Computer science (marked as Mid-importance).
 
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Algorithm[edit]

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

n who, again , pls, create this algo ?!![edit]

i guess O(1) mem n up to O(n*log(n)) time worst performance its too little for a schemsey question like that :P 93.118.212.93 (talk) 10:57, 18 January 2013 (UTC)