स्प्लिसॉर्ट: Difference between revisions
| Line 20: | Line 20: | ||
==विश्लेषण== | ==विश्लेषण== | ||
स्प्ले | स्प्ले ट्री के परिशोधित विश्लेषण के आधार पर, स्प्ले-सॉर्ट का सबसे खराब संचालन समय, n डेटा आइटम वाले इनपुट पर, O(n log n) होता है, जो [[जल्दी से सुलझाएं|क्विकसॉर्ट]], [[ ढेर बनाएं और छांटें |हीप सॉर्ट]] और [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] जैसे प्रभावी गैर-अनुकूल विधिकलनों के लिए समय सीमाओं के समान होता है। | ||
एक इनपुट | जब एक इनपुट क्रम के अनुसार अधिकांश आइटम पूर्ववर्ती के निकट स्थानित होते हैं या केवल कुछ कम आइटम के साथ अव्यवस्थित होते हैं, तब स्प्ले-सॉर्ट, O(n log n) से भी तेज़ हो सकता है, जिससे यह एक अनुकूलनशील सॉर्ट है। इसे परिमाणित करने के लिए, मान लीजिए d<sub>''x''</sub> इनपुट में पदों की संख्या हो जो x को उसके पूर्ववर्ती से अलग करती है, और i<sub>''x''</sub> इनपुट में x के एक तरफ और आउटपुट में x के दूसरी तरफ दिखाई देने वाली वस्तुओं की संख्या है। यदि स्प्ले ट्री के लिए डायनेमिक फिंगर सिद्धांत का पालन किया जाए, तो स्प्ले-सॉर्ट के लिए कुल समय निम्नलिखित रूप से सीमित होता है। | ||
:<math>\sum_x \log d_x</math> | :<math>\sum_x \log d_x</math> | ||
और | और | ||
:<math>\sum_x \log i_x</math>.<ref>{{citation | :<math>\sum_x \log i_x</math>.<ref>{{citation | ||
| last = Cole | first = Richard | | last = Cole | first = Richard | ||
| Line 35: | Line 35: | ||
| volume = 30 | | volume = 30 | ||
| year = 2000| citeseerx = 10.1.1.36.2713 | | year = 2000| citeseerx = 10.1.1.36.2713 | ||
}}.</ref> | }}.</ref> से | ||
स्प्लेसॉर्ट को इनपुट अनुक्रम के [[एन्ट्रॉपी (सूचना सिद्धांत)]] के अनुकूल भी | स्प्लेसॉर्ट को इनपुट अनुक्रम के [[एन्ट्रॉपी (सूचना सिद्धांत)|एन्ट्रॉपी]] के अनुकूल भी दर्शाया जा सकता है।<ref>{{citation | ||
| last = Gagie | first = Travis | | last = Gagie | first = Travis | ||
| arxiv = cs/0506027 | | arxiv = cs/0506027 | ||
Revision as of 23:59, 19 July 2023
कंप्यूटर विज्ञान में, स्प्ले-सॉर्ट, एक स्प्ले ट्री डेटा संरचना पर आधारित अनुकूलन संबंधी तुलना सॉर्टिंग विधिकलन है।[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]
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.
