स्प्लिसॉर्ट
कंप्यूटर विज्ञान में, स्प्ले-सॉर्ट, एक स्प्ले ट्री डेटा संरचना पर आधारित अनुकूलन संबंधी तुलना सॉर्टिंग विधिकलन है।[1]
विधिकलन
विधिकलन के चरण हैं:
- एक रिक्त स्प्ले ट्री का चयन करें
- इनपुट क्रम में प्रत्येक डेटा आइटम के लिए, इसे स्प्ले ट्री में प्रविष्ट करें। इन्सर्शन
- डेटा के लिए सम्मिलिति करने के उपरांत, स्प्ले ट्री को क्रमबद्ध करें ताकि डेटा की क्रमबद्धता का पता चले।
इस प्रकार, विधिकलन को इन्सर्शन सॉर्ट या ट्री सॉर्ट के रूप में देखा जा सकता है, जहाँ प्रत्येक इन्सर्शन को गति देने के लिए एक स्प्ले ट्री का उपयोग किया जाता है।
विश्लेषण
स्प्ले पेड़ों के अमूर्त विश्लेषण के आधार पर, एन डेटा आइटम के साथ इनपुट पर स्प्लेसॉर्ट का सबसे खराब समय चलने वाला समय ओ (एन लॉग एन) है, जो जल्दी से सुलझाएं, ढेर बनाएं और छांटें जैसे कुशल गैर-अनुकूली विधिकलन के लिए समय सीमा से मेल खाता है। और मर्ज़ सॉर्ट करें।
एक इनपुट अनुक्रम के लिए जिसमें अधिकांश वस्तुओं को क्रमबद्ध क्रम में उनके पूर्ववर्ती के करीब रखा जाता है, या केवल कुछ अन्य वस्तुओं के साथ क्रम से बाहर होते हैं, स्प्लेसॉर्ट ओ (एन लॉग एन) से तेज़ हो सकता है, यह दर्शाता है कि यह एक है अनुकूली प्रकार. इसे परिमाणित करने के लिए, मान लीजिए dx इनपुट में पदों की संख्या हो जो x को उसके पूर्ववर्ती से अलग करती है, और चलो ix इनपुट में x के एक तरफ और आउटपुट में x के दूसरी तरफ दिखाई देने वाली वस्तुओं की संख्या (व्युत्क्रम (असतत गणित) की संख्या जिसमें x शामिल है)। फिर यह स्प्ले पेड़ों के लिए गतिशील उंगली प्रमेय से निम्नानुसार है कि स्प्लेसॉर्ट के लिए कुल समय किसके द्वारा सीमित है
और तक
- .[2]
स्प्लेसॉर्ट को इनपुट अनुक्रम के एन्ट्रॉपी (सूचना सिद्धांत) के अनुकूल भी दिखाया जा सकता है।[3]
प्रयोगात्मक परिणाम
द्वारा प्रयोगों में Moffat, Eddy & Petersson (1996), स्प्लेसॉर्ट 1.5 से 2 के कारक द्वारा यादृच्छिक संख्याओं की तालिकाओं पर क्विकॉर्ट की तुलना में धीमा था, और छोटे कारकों द्वारा मर्जसॉर्ट की तुलना में धीमा था। बड़े रिकॉर्ड वाले डेटा के लिए, फिर से एक यादृच्छिक क्रम में, क्विकॉर्ट द्वारा किए गए डेटा मूवमेंट की अतिरिक्त मात्रा ने पॉइंटर-आधारित विधिकलन की तुलना में इसे काफी धीमा कर दिया, और स्प्लेसॉर्ट और मर्जसॉर्ट का समय एक-दूसरे के बहुत करीब था। हालाँकि, लगभग पूर्व-निर्धारित इनपुट अनुक्रमों के लिए (डेटा में सन्निहित मोनोटोन अनुवर्ती की संख्या, व्युत्क्रमों की संख्या, क्रमबद्ध अनुवर्ती बनाने के लिए हटाए जाने वाले आइटमों की संख्या, या गैर-सन्निहित मोनोटोन अनुवर्ती की संख्या के संदर्भ में मापा जाता है) जिसमें इनपुट को विभाजित किया जा सकता है) स्प्लेसॉर्ट अन्य विधिकलन की तुलना में काफी अधिक कुशल हो गया।[1]
Elmasry & Hammad (2005)स्प्लेसॉर्ट की तुलना कई अन्य विधिकलन से की गई है जो इनपुट में व्युत्क्रमों की कुल संख्या के साथ-साथ क्विकसॉर्ट के लिए अनुकूली हैं। उन्होंने पाया कि, उन इनपुटों पर जिनमें क्विकॉर्ट की तुलना में अनुकूली विधिकलन को तेज़ बनाने के लिए पर्याप्त व्युत्क्रमण कम थे, स्प्लेसॉर्ट सबसे तेज़ विधिकलन था।[4]
भिन्नताएँ
Saikkonen & Soisalon-Soininen (2012) इनपुट में सन्निहित मोनोटोन अनुवर्ती की संख्या के लिए अधिक दृढ़ता से अनुकूली होने के लिए स्प्लेसॉर्ट को संशोधित करें, और प्रयोगों पर रिपोर्ट करें जो दर्शाता है कि परिणामी विधिकलन उन इनपुटों पर तेज़ है जो इस माप के अनुसार लगभग पूर्व-सॉर्ट किए गए हैं।[5]
संदर्भ
- ↑ 1.0 1.1 Moffat, Alistair; Eddy, Gary; Petersson, Ola (July 1996), "Splaysort: Fast, Versatile, Practical", Software: Practice and Experience, 26 (7): 781–797, doi:10.1002/(SICI)1097-024X(199607)26:7<781::AID-SPE35>3.3.CO;2-2
- ↑ Cole, Richard (2000), "On the dynamic finger conjecture for splay trees. II. The proof", SIAM Journal on Computing, 30 (1): 44–85, CiteSeerX 10.1.1.36.2713, doi:10.1137/S009753979732699X, MR 1762706.
- ↑ Gagie, Travis (2005), Sorting a low-entropy sequence, arXiv:cs/0506027, Bibcode:2005cs........6027G.
- ↑ Elmasry, Amr; Hammad, Abdelrahman (2005), "An empirical study for inversions-sensitive sorting algorithms", Experimental and Efficient Algorithms: 4th International Workshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3503, Springer, pp. 597–601, doi:10.1007/11427186_52.
- ↑ Saikkonen, Riku; Soisalon-Soininen, Eljas (2012), "A general method for improving insertion-based adaptive sorting", Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7676, Springer, pp. 217–226, doi:10.1007/978-3-642-35261-4_25.
