टूर्नामेंट क्रम

टूर्नामेंट क्रम

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n log n)
Average performance	O(n log 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]

संदर्भ

• Kershenbaum et al 1988, "Higher Order Imperative Programming"