स्प्लिसॉर्ट
कंप्यूटर विज्ञान में, स्प्लेसॉर्ट, बिखरा हुआ पेड़ डेटा संरचना पर आधारित एक अनुकूली सॉर्ट तुलना सॉर्टिंग कलन विधि है।[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.
