स्प्लिसॉर्ट
कंप्यूटर विज्ञान में, स्प्ले-सॉर्ट, एक स्प्ले ट्री डेटा संरचना पर आधारित अनुकूलन संबंधी तुलना सॉर्टिंग विधिकलन है।[1]
विधिकलन
स्प्ले-सॉर्ट विधिकलन के निम्नलिखित चरण हैं:
- एक रिक्त स्प्ले ट्री का चयन करें
- इनपुट क्रम में प्रत्येक डेटा आइटम के लिए, इसे स्प्ले ट्री में प्रविष्ट करें। इन्सर्शन
- डेटा के लिए सम्मिलिति करने के उपरांत, स्प्ले ट्री को क्रमबद्ध करें ताकि डेटा की क्रमबद्धता का पता चले।
इस प्रकार, विधिकलन को इन्सर्शन सॉर्ट या ट्री सॉर्ट के रूप में देखा जा सकता है, जहाँ प्रत्येक इन्सर्शन को गति देने के लिए एक स्प्ले ट्री का उपयोग किया जाता है।
विश्लेषण
स्प्ले ट्री के परिशोधित विश्लेषण के आधार पर, स्प्ले-सॉर्ट का सबसे खराब संचालन समय, n डेटा आइटम वाले इनपुट पर, O(n log n) होता है, जो क्विकसॉर्ट, हीप सॉर्ट और मर्ज़ सॉर्ट जैसे प्रभावी गैर-अनुकूल विधिकलनों के लिए समय सीमाओं के समान होता है।
जब एक इनपुट क्रम के अनुसार अधिकांश आइटम पूर्ववर्ती के निकट स्थानित होते हैं या केवल कुछ कम आइटम के साथ अव्यवस्थित होते हैं, तब स्प्ले-सॉर्ट, O(n log n) से भी तेज़ हो सकता है, जिससे यह एक अनुकूलनशील सॉर्ट है। इसे परिमाणित करने के लिए, मान लीजिए dx इनपुट में पदों की संख्या हो जो x को उसके पूर्ववर्ती से अलग करती है, और ix इनपुट में x के एक तरफ और आउटपुट में x के दूसरी तरफ दिखाई देने वाली वस्तुओं की संख्या है। यदि स्प्ले ट्री के लिए डायनेमिक फिंगर सिद्धांत का पालन किया जाए, तो स्प्ले-सॉर्ट के लिए कुल समय निम्नलिखित रूप से सीमित होता है।
और
- .[2] से
स्प्लेसॉर्ट को इनपुट अनुक्रम के एन्ट्रॉपी के अनुकूल भी दर्शाया जा सकता है।[3]
प्रयोगात्मक परिणाम
Moffat, Eddy & Petersson (1996) के प्रयोगों में, यादृच्छिक संख्याओं की सारणियों पर स्प्ले सॉर्ट क्विकसॉर्ट से 1.5 से 2 गुना धीमा था, और मर्जसॉर्ट से छोटे गुणांकों से भी धीमा था। बड़े रिकॉर्ड वाले डेटा के लिए, पुनः एक यादृच्छिक क्रम में, क्विकसॉर्ट द्वारा किए गए डेटा प्रसार की अतिरिक्त मात्रा ने पॉइंटर-आधारित विधिकलन की तुलना में इसे अत्यधिक धीमा कर दिया, और स्प्लेसॉर्ट और मर्जसॉर्ट का समय परस्पर निकट था। यद्यपि तथ्यों के आधार पर, लगभग सॉर्ट किए गए इनपुट सिरजनहारों के लिए (डेटा में एकत्रित मोनोटोन सबस्ट्रिंग की संख्या, विपरीतताओं की संख्या, एक सॉर्टेड सबस्ट्रिंग बनाने के लिए हटाए जाने वाले आइटमों की संख्या, या इनपुट को विभाजित किया जा सकने वाले गैर-एकत्रित मोनोटोन सबस्ट्रिंग की संख्या की मापन में), स्प्ले सॉर्ट अन्य विधिकलनों से अत्यधिक कुशल हो गया।[1]
एलमास्री & हम्माद (2005) ने स्प्लेसॉर्ट की तुलना क्विकसॉर्ट के साथ-साथ कई अन्य विधिकलनों से की, जो इनपुट में व्युत्क्रमों की कुल संख्या के साथ अनुकूली हैं। उन्होंने पाया कि, उन इनपुटों पर जिनमें क्विकसॉर्ट की तुलना में अनुकूली विधिकलन को तेज़ बनाने के लिए पर्याप्त व्युत्क्रमण कम थे, स्प्लेसॉर्ट सबसे तेज विधिकलन था।[4]
भिन्नताएँ
साइकोनेन & सोइसालोन-सोइनिनन (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.
