Turnir sort

	Turnir sort
Namena	Algoritam za sortiranje
Struktura podataka	niz
Vremenska kompl.	O(n log n)

Turnir sort je algoritam za sortiranje. Unapređuje naivno sortiranje selekcijom koristeći prioritetni red radi nalaženja sledećeg elementa u nizu. Sortiranjem selekcijom, potrebno je O(n) operacija kako bi se odabrao idući od n elemenata; u turnir sortiranju, potrebno je O(log n) operacija (nakon kreiranja početnog turnira u vremenu O(n)). Turnir sort je varijacija hipsorta.^[1]

Česta implementacija[uredi | uredi izvor]

Sortiranja selekcijom za zamenu turnira se koriste kako bi se prikupila početna stanja za spoljašnje algoritme za sortiranje. Konceptualno, spoljašnja datoteka se čita, i njeni elementi se stavljaju u prioritetni red dok se on ne napuni. Onda se minimalni element izvadi iz reda i označi se kao deo prvog kruga. Sledeći ulazni element se čita i stavlja u red, i minimum se ponovo bira i stavlja u krug. Ako je novi element, koji se stavlja u red, manji od poslednjeg elementa koji je dodat u krug, onda se vrednost sortiranja elementa uveća, tako da on bude deo sledećeg kruga. U proseku, krug će biti 100% duži nego kapacitet prioritetnog reda.^[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]

Turnir[uredi | uredi izvor]

Ime dolazi iz njegove sličnosti sa eliminacionim turnirom u kome više igrača ili timova igraju u "jedan na jedan" mečevima gde gubitnik ispada iz turnira, a pobednik ide u sledeći krug. Proces se nastavlja do finalnog meča, koji odlučuje pobednika turnira. Turnir daje najboljeg igrača, ali igrač koji je izgubio u finalu ne mora biti drugi najbolji, već može biti i lošiji od drugih igrača koje je pobednik izbacio iz turnira.^[3]