|
Турнир сорт је алгоритам за сортирање. Унапређује наивно сортирање селекцијом користећи приоритетни ред ради налажења следећег елемента у низу. Сортирањем селекцијом, потребно је O(n) операција како би се одабрао идући од n елемената; у турнир сортирању, потребно је O(log n) операција (након креирања почетног турнира у времену O(n)). Турнир сорт је варијација хипсорта.[1]
Сортирања селекцијом за замену турнира се користе како би се прикупила почетна стања за спољашње алгоритме за сортирање. Концептуално, спољашња датотека се чита, и њени елементи се стављају у приоритетни ред док се он не напуни. Онда се минимални елемент извади из реда и означи се као део првог круга. Следећи улазни елемент се чита и ставља у ред, и минимум се поново бира и ставља у круг. Ако је нови елемент, који се ставља у ред, мањи од последњег елемента који је додат у круг, онда се вредност сортирања елемента увећа, тако да он буде део следећег круга. У просеку, круг ће бити 100% дужи него капацитет приоритетног реда.[2]
import Data.Tree
-- | Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report.
tournamentSort :: Ord t
=> [t] -- ^ Input: an unsorted list
-> [t] -- ^ 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 [tree] = 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 [tree] done = 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 {
rootLabel = rootLabel winner,
subForest = loser : subForest winner}
main :: IO ()
main = print $ tournamentSort testList
where testList = [0, 1, 2, 3, 4, 5]
Име долази из његове сличности са елиминационим турниром у коме више играча или тимова играју у "један на један" мечевима где губитник испада из турнира, а победник иде у следећи круг. Процес се наставља до финалног меча, који одлучује победника турнира. Турнир даје најбољег играча, али играч који је изгубио у финалу не мора бити други најбољи, већ може бити и лошији од других играча које је победник избацио из турнира.[3]