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

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

Class	सॉर्टिंग एल्गोरिदम
Data structure	ऐरे
Worst-case performance	O(n log n)
Average performance	O(n log n)

टूर्नामेंट क्रम एक श्रेणीकरण एल्गोरिदम है। यह क्रम में अगला अवयव ढूंढने के लिए प्राथमिकता पंक्ति का उपयोग करके सरल चयन क्रम में सुधार करता है। अनुभवहीन चयन क्रम में, n अवयवों के अगले अवयव का चयन करने के लिए O(n) संक्रिया की आवश्यकता होती है; टूर्नामेंट क्रम में, इसमें O(log n) संक्रिया होते हैं O(n) में प्रारंभिक टूर्नामेंट बनाने के बाद)। टूर्नामेंट क्रम, हीप्सॉर्ट का ही एक रूप है।

सामान्य अनुप्रयोग

टूर्नामेंट प्रतिस्थापन चयन क्रम का उपयोग बाहरी श्रेणीकरण एल्गोरिदम के लिए प्रारंभिक रन संगृहीत करने के लिए किया जाता है। वैचारिक रूप से, एक बाहरी फ़ाइल पढ़ी जाती है और उसके अवयवों को प्राथमिकता पंक्ति में जोड़ दिया जाता है जब तक कि पंक्ति पूरी न हो जाए। न्यूनतम अवयव को फिर पंक्ति से निकाला जाता है और पहले रन के भाग के रूप में लिखा जाता है। अगले इनपुट अवयव को पढ़ा जाता है और पंक्ति में डाल दिया जाता है, और मिनट को फिर से चुना जाता है और रन में जोड़ा जाता है। एक छोटी सी युक्ति है कि यदि पंक्ति में जोड़ा जाने वाला नया अवयव रन में जोड़े गए अंतिम अवयव से कम है, तो अवयव का क्रम मान बढ़ जाता है, इसलिए यह अगले रन का भाग होगा, इसलिए यह अगले रन का भाग होगा। औसतन, एक रन प्राथमिकता पंक्ति की क्षमता से 100% दीर्घ होगा।

टूर्नामेंट क्रम का उपयोग n-वे विलय में भी किया जा सकता है।

व्युत्पत्ति

यह नाम इसकी एकल-उन्मूलन टूर्नामेंट से समानता के कारण आया है, जहां कई खिलाड़ी (या टीमें) हैं जो दो-तरफा मैच खेलते हैं। प्रत्येक मैच में खिलाड़ियों की तुलना की जाती है, और विजेता खिलाड़ी को अगले स्तर पर मैच खेलने के लिए पदोन्नत किया जाता है। पदानुक्रम तब तक जारी रहता है जब तक कि अंतिम मैच अंतिम विजेता का निर्धारण न कर दे। टूर्नामेंट सर्वश्रेष्ठ खिलाड़ी का निर्धारण करता है, लेकिन जो खिलाड़ी फाइनल मैच में हार गया था, वह दूसरा सर्वश्रेष्ठ खिलाड़ी नहीं हो सकता है - वह विजेता द्वारा सर्वश्रेष्ठ किये गये अन्य खिलाड़ियों से कमतर हो सकता है।

कार्यान्वयन

निम्नलिखित हास्केल में टूर्नामेंट क्रम का कार्यान्वयन है, जो स्टेपानोव और केरशेनबाम द्वारा योजना कोड पर आधारित है।

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"