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

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

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n log n)
Average performance	O(n log n)

टूर्नामेंट सॉर्ट एक सॉर्टिंग एल्गोरिदम है। यह सॉर्ट में अगला तत्व ढूंढने के लिए प्राथमिकता कतार का उपयोग करके सरल चयन सॉर्ट में सुधार करता है। अनुभवहीन चयन सॉर्ट में, n तत्वों के अगले तत्व का चयन करने के लिए O(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"