Tournament sort is a
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
. It improves upon the naive
selection sort
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is not ...
by using a
priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
to find the next element in the sort. In the naive selection sort, it takes
O(''n'') operations to select the next element of ''n'' elements; in a tournament sort, it takes O(log ''n'') operations (after building the initial tournament in O(''n'')). Tournament sort is a variation of
heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
.
Common application
Tournament replacement selection sorts are used to gather the initial runs for external sorting algorithms. Conceptually, an external file is read and its elements are pushed into the priority queue until the queue is full. Then the minimum element is pulled from the queue and written as part of the first run. The next input element is read and pushed into the queue, and the min is selected again and added to the run. There's a small trick that if the new element being pushed into the queue is less than the last element added to the run, then the element's sort value is increased so it will be part of the next run. On average, a run will be 100% longer than the capacity of the priority queue.
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
, The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
, Sorting and Searching, Volume 3, 1973. The "snowplow" argument. p. 254
Tournament sorts may also be used in N-way merges.
Etymology
The name comes from its similarity to a
single-elimination tournament
A single-elimination, knockout, or sudden death tournament is a type of elimination tournament where the loser of each match-up is immediately eliminated from the tournament. Each winner will play another in the next round, until the final matc ...
where there are many players (or teams) that play in two-sided matches. Each match compares the players, and the winning player is promoted to play a match at the next level up. The hierarchy continues until the final match determines the ultimate winner. The tournament determines the best player, but the player who was beaten in the final match may not be the second best – he may be inferior to other players the winner bested.
Implementation
The following is an implementation of tournament sort in
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lang ...
, based on
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
code by Stepanov and Kershenbaum.
import Data.Tree
-- , Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report.
tournamentSort :: Ord t
=> -- ^ Input: an unsorted list
-> -- ^ Result: sorted version of the input
tournamentSort alist
= go (pure<$>alist) -- first, wrap each element as a single-tree forest
where go [] = []
go trees = (rootLabel winner) : (go (subForest winner))
where winner = playTournament trees
-- , Adapted from `TOURNAMENT!` in the Stepanov and Kershenbaum report
playTournament :: Ord t
=> Forest t -- ^ Input forest
-> Tree t -- ^ The last promoted tree in the input
playTournament ree= tree
playTournament trees = playTournament (playRound trees [])
-- , Adapted from `TOURNAMENT-ROUND!` in the Stepanov and Kershenbaum report
playRound :: Ord t
=> Forest t -- ^ A forest of trees that have not yet competed in round
-> Forest t -- ^ A forest of trees that have won in round
-> Forest t -- ^ Output: a forest containing promoted versions
-- of the trees that won their games
playRound [] done = done
playRound reedone = tree:done
playRound (tree0:tree1:trees) done = playRound trees (winner:done)
where winner = playGame tree0 tree1
-- , Adapted from `TOURNAMENT-PLAY!` in the Stepanov and Kershenbaum report
playGame :: Ord t
=> Tree t -- ^ Input: ...
-> Tree t -- ^ ... two trees
-> Tree t -- ^ Result: `promote winner loser`, where `winner` is
-- the tree with the *lesser* root of the two inputs
playGame tree1 tree2
, rootLabel tree1 <= rootLabel tree2 = promote tree1 tree2
, otherwise = promote tree2 tree1
-- , Adapted from `GRAB!` in the Stepanov and Kershenbaum report
promote :: Tree t -- ^ The `winner`
-> Tree t -- ^ The `loser`
-> Tree t -- ^ Result: a tree whose root is the root of `winner`
-- and whose children are:
-- * `loser`,
-- * all the children of `winner`
promote winner loser = Node
main :: IO ()
main = print $ tournamentSort testList
where testList = , 1, 2, 3, 4, 5
References
* Kershenbaum et al 1988
"Higher Order Imperative Programming"
{{sorting
Sorting algorithms