Турнир сорт

Турнир сорт

Намена Алгоритам за сортирање Структура података низ Временска компл. O(n log n)

Турнир сорт је алгоритам за сортирање. Унапређује наивно сортирање селекцијом користећи приоритетни ред ради налажења следећег елемента у низу. Сортирањем селекцијом, потребно је O(n) операција како би се одабрао идући од n елемената; у турнир сортирању, потребно је O(log n) операција (након креирања почетног турнира у времену O(n)). Турнир сорт је варијација хипсорта.

Честа имплементација

Сортирања селекцијом за замену турнира се користе како би се прикупила почетна стања за спољашње алгоритме за сортирање. Концептуално, спољашња датотека се чита, и њени елементи се стављају у приоритетни ред док се он не напуни. Онда се минимални елемент извади из реда и означи се као део првог круга. Следећи улазни елемент се чита и ставља у ред, и минимум се поново бира и ставља у круг. Ако је нови елемент, који се ставља у ред, мањи од последњег елемента који је додат у круг, онда се вредност сортирања елемента увећа, тако да он буде део следећег круга. У просеку, круг ће бити 100% дужи него капацитет приоритетног реда.

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]

Турнир

Име долази из његове сличности са елиминационим турниром у коме више играча или тимова играју у "један на један" мечевима где губитник испада из турнира, а победник иде у следећи круг. Процес се наставља до финалног меча, који одлучује победника турнира. Турнир даје најбољег играча, али играч који је изгубио у финалу не мора бити други најбољи, већ може бити и лошији од других играча које је победник избацио из турнира.

Види још

• Селекциони алгоритам