स्मूथसॉर्ट
 Smoothsort operating on an array which is mostly in order. The bars across the top show the tree structure. | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n log n) |
| Best-case performance | O(n) |
| Average performance | O(n log n) |
| Worst-case space complexity | O(n) total, O(1) auxiliary |
कंप्यूटर विज्ञान में, स्मूथसॉर्ट एक तुलनात्मक सॉर्ट|तुलना-आधारित छँटाई एल्गोरिथ्म है। ढेर बनाएं और छांटें का एक प्रकार, इसका आविष्कार और प्रकाशन 1981 में एडवर्ड डिज्क्स्ट्रा द्वारा किया गया था।[1] हीपसॉर्ट की तरह, स्मूथसॉर्ट एक इन-प्लेस एल्गोरिदम है जिसकी ऊपरी सीमा होती है O(n log n),[2] लेकिन यह एक स्थिर प्रकार नहीं है।[3][self-published source?][4] स्मूथसॉर्ट का लाभ यह है कि यह करीब आता है O(n) समय यदि अनुकूली प्रकार है, जबकि हीपसॉर्ट औसत है O(n log n) प्रारंभिक क्रमबद्ध स्थिति की परवाह किए बिना।
अवलोकन
हीप्सॉर्ट की तरह, स्मूथसॉर्ट इनपुट को प्राथमिकता कतार में व्यवस्थित करता है और फिर बार-बार अधिकतम निकालता है। हीप्सोर्ट की तरह, प्राथमिकता कतार एक अंतर्निहित डेटा संरचना हीप डेटा संरचना (एक हीप (डेटा संरचना)-आदेशित अंतर्निहित द्विआधारी वृक्ष ) है, जो सरणी के एक उपसर्ग पर कब्जा कर लेती है। प्रत्येक निष्कर्षण उपसर्ग को सिकोड़ता है और निकाले गए तत्व को बढ़ते हुए क्रमबद्ध प्रत्यय में जोड़ता है। जब उपसर्ग सिकुड़कर शून्य हो जाता है, तो सरणी पूरी तरह से क्रमबद्ध हो जाती है।
हीपसॉर्ट पेड़ के शीर्ष-नीचे चौड़ाई-प्रथम ट्रैवर्सल का उपयोग करके बाइनरी ट्री को सरणी में मैप करता है; सरणी पेड़ की जड़ से शुरू होती है, फिर उसके दो बच्चे, फिर चार पोते-पोतियाँ, और इसी तरह। प्रत्येक तत्व की पेड़ की जड़ के नीचे एक अच्छी तरह से परिभाषित गहराई होती है, और जड़ को छोड़कर प्रत्येक तत्व का मूल तत्व सरणी में पहले होता है। हालाँकि, पत्तियों के ऊपर इसकी ऊँचाई सरणी के आकार पर निर्भर करती है। इसका नुकसान यह है कि प्रत्येक तत्व को सॉर्टिंग प्रक्रिया के हिस्से के रूप में स्थानांतरित किया जाना चाहिए: इसे अपने अंतिम स्थान पर ले जाने से पहले रूट से गुजरना होगा।
स्मूथसॉर्ट एक अलग मैपिंग, बॉटम-अप डेप्थ-फर्स्ट ट्री ट्रैवर्सल#पोस्ट-ऑर्डर, एलआरएन|पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करता है। बाएं बच्चे का अनुसरण उसके भाई-बहन में निहित उपवृक्ष द्वारा किया जाता है, और दाएं बच्चे का अनुसरण उसके माता-पिता द्वारा किया जाता है। प्रत्येक तत्व की पत्तियों के ऊपर एक अच्छी तरह से परिभाषित ऊंचाई होती है, और प्रत्येक गैर-पत्ती तत्व के बच्चे सरणी में पहले होते हैं। हालाँकि, जड़ के नीचे इसकी गहराई सरणी के आकार पर निर्भर करती है। एल्गोरिथ्म को व्यवस्थित किया गया है ताकि जड़ ढेर के अंत में हो, और जिस समय एक तत्व ढेर से निकाला जाता है वह पहले से ही अपने अंतिम स्थान पर होता है और उसे स्थानांतरित करने की आवश्यकता नहीं होती है। इसके अलावा, एक क्रमबद्ध सरणी पहले से ही एक वैध ढेर है, और कई क्रमबद्ध अंतराल वैध ढेर-आदेशित उपवृक्ष हैं।
अधिक औपचारिक रूप से, हर स्थिति i एक अद्वितीय उपवृक्ष की जड़ है, जिसके नोड्स एक सन्निहित अंतराल पर होते हैं जो समाप्त होता है i. सरणी का एक प्रारंभिक उपसर्ग (संपूर्ण सरणी सहित), एक उपवृक्ष के अनुरूप एक ऐसा अंतराल हो सकता है, लेकिन सामान्य तौर पर यह ऐसे कई क्रमिक उपवृक्ष अंतरालों के संघ के रूप में विघटित होता है, जिसे डिज्क्स्ट्रा स्ट्रेच कहते हैं। माता-पिता के बिना कोई भी उपवृक्ष (अर्थात ऐसी स्थिति में निहित है जिसका माता-पिता विचाराधीन उपसर्ग से परे है) उस अंतराल के अपघटन में एक खिंचाव देता है, इसलिए यह अपघटन अद्वितीय है। जब एक नया नोड उपसर्ग में जोड़ा जाता है, तो दो मामलों में से एक होता है: या तो स्थिति एक पत्ती है और अपघटन में लंबाई 1 का खिंचाव जोड़ती है, या यह अंतिम दो हिस्सों के साथ जुड़ती है, उनकी संबंधित जड़ों का जनक बन जाती है, इस प्रकार दो हिस्सों को एक नए हिस्से से बदल दिया जाता है जिसमें उनका मिलन और नई (रूट) स्थिति शामिल होती है।
दिज्क्स्ट्रा ने नोट किया[1] कि स्पष्ट नियम यह होगा कि स्ट्रेच को केवल तभी संयोजित किया जाए जब उनका आकार समान हो, उस स्थिति में सभी उपवृक्ष आकार के सही बाइनरी पेड़ होंगे 2k−1. हालाँकि, उन्होंने एक अलग नियम चुना, जो पेड़ों के अधिक संभावित आकार देता है। इसमें वही एसिम्प्टोटिक विश्लेषण है,[2] लेकिन प्रत्येक अंतराल को कवर करने के लिए कम विस्तार की आवश्यकता के कारण दक्षता में एक छोटा स्थिर कारक प्राप्त होता है।
डिज्क्स्ट्रा जिस नियम का उपयोग करता है वह यह है कि अंतिम दो हिस्सों को संयोजित किया जाता है यदि और केवल तभी जब उनका आकार लगातार लियोनार्डो संख्या हो L(i+1) और L(i) (उस क्रम में), किन संख्याओं को पुनरावर्ती रूप से परिभाषित किया गया है, फाइबोनैचि संख्याओं के समान ही, जैसे:
- L(0) = L(1) = 1
- L(k+2) = L(k+1) + L(k) + 1
परिणामस्वरूप, किसी भी उपवृक्ष का आकार लियोनार्डो संख्या है। खिंचाव के आकार का क्रम पहले विघटित होता है nपद, किसी के लिए n, लालची तरीके से पाया जा सकता है: पहला आकार सबसे बड़ा लियोनार्डो संख्या से अधिक नहीं है n, और शेष (यदि कोई हो) पुनरावर्ती रूप से विघटित हो जाता है। स्ट्रेच के आकार कम हो रहे हैं, संभवतः दो अंतिम आकार 1 को छोड़कर, और संभवतः अंतिम दो आकारों को छोड़कर क्रमिक लियोनार्डो संख्याओं से परहेज किया जा रहा है।
प्रत्येक खंड ढेर-क्रम वाले पेड़ होने के अलावा, पेड़ों की जड़ों को क्रमबद्ध क्रम में बनाए रखा जाता है। यह प्रभावी रूप से प्रत्येक रूट में एक तीसरा बच्चा (जिसे दिज्क्स्ट्रा सौतेला बेटा कहता है) जोड़ता है और इसे पिछले रूट से जोड़ता है। यह सभी पेड़ों को एक साथ एक वैश्विक ढेर में जोड़ता है। अंत में वैश्विक अधिकतम के साथ।
यद्यपि प्रत्येक नोड के स्टेपसन का स्थान निश्चित है, लिंक केवल पेड़ की जड़ों के लिए मौजूद है, जिसका अर्थ है कि जब भी पेड़ विलय होते हैं तो लिंक हटा दिए जाते हैं। यह आम बच्चों से अलग है, जो तब तक जुड़े रहते हैं जब तक माता-पिता मौजूद हैं।
छँटाई के पहले (ढेर बढ़ने) चरण में, सरणी के एक बड़े प्रारंभिक भाग को पुनर्गठित किया जाता है ताकि इसके प्रत्येक विस्तार के लिए उपवृक्ष अधिकतम-ढेर हो: किसी भी गैर-पत्ती स्थिति में प्रविष्टि कम से कम उतनी बड़ी हो उन पदों पर प्रविष्टियाँ जो उसके बच्चे हैं। इसके अलावा, सभी जड़ें कम से कम उनके सौतेले बेटे जितनी बड़ी होती हैं।
दूसरे (ढेर सिकुड़न) चरण में, अधिकतम नोड को सरणी के अंत से अलग कर दिया जाता है (इसे स्थानांतरित करने की आवश्यकता के बिना) और ढेर अपरिवर्तनीय को उसके बच्चों के बीच फिर से स्थापित किया जाता है। (विशेषकर, नव निर्मित सौतेलों के बीच।)
व्यावहारिक कार्यान्वयन के लिए अक्सर लियोनार्डो संख्याओं की गणना करने की आवश्यकता होती है L(k). डिज्क्स्ट्रा चतुर कोड प्रदान करता है जो आवश्यक समय पर आवश्यक मूल्यों की कुशलतापूर्वक गणना करने के लिए निश्चित संख्या में पूर्णांक चर का उपयोग करता है। वैकल्पिक रूप से, यदि कोई परिमित सीमा है N क्रमबद्ध किए जाने वाले सरणियों के आकार पर, लियोनार्डो संख्याओं की एक पूर्व-गणना की गई तालिका को संग्रहीत किया जा सकता है O(log N) अंतरिक्ष।
संचालन
जहां तक ढेरों के अनुक्रम संरचना के विकास का सवाल है, छँटाई प्रक्रिया के दो चरण एक-दूसरे के विपरीत हैं, उन्हें एक कोर आदिम का उपयोग करके कार्यान्वित किया जाता है, जो कि के बराबर है।
बाइनरी मैक्स-हीप में ऑपरेशन को सिफ्ट करें।
छानना
कोर सिफ्ट-डाउन ऑपरेशन (जिसे डिज्क्स्ट्रा विक्ट:ट्रिंकल कहता है) हीप इनवेरिएंट को तब पुनर्स्थापित करता है जब इसका संभवतः केवल रूट नोड पर उल्लंघन किया जाता है। यदि रूट नोड अपने किसी भी बच्चे से कम है, तो इसे उसके सबसे बड़े बच्चे के साथ बदल दिया जाता है और प्रक्रिया को उसके नए उपट्री में रूट नोड के साथ दोहराया जाता है।
स्मूथसॉर्ट और बाइनरी मैक्स-हीप के बीच अंतर यह है कि प्रत्येक स्ट्रेच की जड़ को तीसरे स्टेपसन के संबंध में क्रमबद्ध किया जाना चाहिए: पूर्ववर्ती स्ट्रेच की जड़। तो सिफ्ट-डाउन प्रक्रिया चार-तरफा तुलनाओं (रूट नोड और तीन बच्चों) की एक श्रृंखला के साथ शुरू होती है जब तक कि स्टेप्सन अधिकतम तत्व नहीं होता है, फिर तीन-तरफा तुलनाओं की एक श्रृंखला (रूट प्लस दो बच्चे) रूट तक नोड को अपना अंतिम घर मिल जाता है और अपरिवर्तनीय पुनः स्थापित हो जाते हैं।
प्रत्येक पेड़ एक बाइनरी ट्री है#बाइनरी ट्री के प्रकार: प्रत्येक नोड में दो बच्चे होते हैं या एक भी नहीं। एक बच्चे के विशेष मामले से निपटने की कोई आवश्यकता नहीं है जो एक मानक अंतर्निहित बाइनरी ढेर में होता है। (लेकिन सौतेले बेटे के लिंक का विशेष मामला इस बचत की भरपाई करता है।)
क्योंकि वहाँ हैं O(log n) विस्तार, जिनमें से प्रत्येक गहराई का एक वृक्ष है O(log n), प्रत्येक सिफ्टिंग-डाउन ऑपरेशन को करने का समय निर्धारित है O(log n).
दाईं ओर एक तत्व को शामिल करके ढेर क्षेत्र को बढ़ाना
जब एक अतिरिक्त तत्व को स्ट्रेच के अनुक्रम (असंयुक्त ढेर संरचनाओं की सूची) में शामिल करने पर विचार किया जाता है, तो यह या तो एक नया एक-तत्व स्ट्रेच बनाता है, या यह दोनों जड़ों के माता-पिता बनकर दो सबसे दाहिने स्ट्रेच को जोड़ता है और एक नया स्ट्रेच बनाता है। जो क्रम में दोनों को प्रतिस्थापित करता है। दोनों में से क्या होता है यह केवल वर्तमान में मौजूद हिस्सों के आकार पर निर्भर करता है (और अंततः केवल जोड़े गए तत्व के सूचकांक पर); डिज्क्स्ट्रा ने निर्धारित किया कि स्ट्रेच को तभी संयोजित किया जाता है जब उनके आकार हों L(k+1) और L(k) कुछ के लिए k, यानी, लगातार लियोनार्डो संख्या; नए खंड का आकार होगा L(k+2).
किसी भी स्थिति में, नए तत्व को ढेर संरचना में उसके सही स्थान पर स्थानांतरित किया जाना चाहिए। भले ही नया नोड एक-तत्व खिंचाव है, फिर भी इसे पिछले खिंचाव की जड़ के सापेक्ष क्रमबद्ध किया जाना चाहिए।
अनुकूलन
दिज्क्स्ट्रा का एल्गोरिदम यह देखकर काम बचाता है कि बढ़ते चरण के अंत में पूर्ण ढेर अपरिवर्तनीय की आवश्यकता होती है, लेकिन प्रत्येक मध्यवर्ती चरण पर इसकी आवश्यकता नहीं होती है। विशेष रूप से, यह आवश्यकता कि कोई तत्व अपने सौतेले बेटे से बड़ा हो, केवल उन तत्वों के लिए महत्वपूर्ण है जो अंतिम पेड़ की जड़ें हैं।
इसलिए, जब कोई तत्व जोड़ा जाता है, तो उसके भावी मूल तत्व की स्थिति की गणना करें। यदि यह क्रमबद्ध किए जाने वाले शेष मानों की सीमा के भीतर है, तो ऐसे कार्य करें जैसे कि कोई सौतेला बेटा नहीं है और केवल वर्तमान पेड़ के भीतर ही छांटें।
सबसे दाहिने तत्व को अलग करके ढेर क्षेत्र को छोटा करना
इस चरण के दौरान, खिंचाव के अनुक्रम का रूप बढ़ते चरण के परिवर्तनों से उलटा होता है। एक पत्ती नोड को अलग करते समय किसी भी काम की आवश्यकता नहीं होती है, लेकिन एक गैर-पत्ती नोड के लिए इसके दो बच्चे नए हिस्सों की जड़ें बन जाते हैं, और हिस्सों की जड़ों के क्रम में उन्हें उनके उचित स्थान पर ले जाने की आवश्यकता होती है। इसे दो बार सिफ्ट-डाउन लागू करके प्राप्त किया जा सकता है: पहले बाएं बच्चे के लिए, और फिर दाएं बच्चे के लिए (जिसका सौतेला बेटा बायां बच्चा था)।
क्योंकि एक पूर्ण बाइनरी ट्री में सभी नोड्स में से आधे पत्ते होते हैं, यह प्रति नोड औसतन एक सिफ्ट-डाउन ऑपरेशन करता है।
अनुकूलन
यह पहले से ही ज्ञात है कि नई उजागर जड़ें अपने सामान्य बच्चों के संबंध में सही ढंग से क्रमबद्ध हैं; यह केवल उनके सौतेले बेटों से संबंधित आदेश है जो प्रश्न में है। इसलिए, ढेर को सिकोड़ते समय, नीचे छानने के पहले चरण को सौतेले बेटे के साथ तुलना करके सरल बनाया जा सकता है। यदि कोई अदला-बदली होती है, तो अगले चरणों में पूर्ण चार-तरफ़ा तुलना करनी होगी।
विश्लेषण
स्मूथसॉर्ट लेता है O(n) एक निर्दिष्ट सरणी को संसाधित करने का समय, O(n log n) सबसे खराब स्थिति में, और कई लगभग-क्रमबद्ध इनपुट पर लगभग-रैखिक प्रदर्शन प्राप्त करता है। हालाँकि, यह सभी लगभग-क्रमबद्ध अनुक्रमों को बेहतर ढंग से संभाल नहीं पाता है। अन-सॉर्टेडनेस (सूचकांकों के जोड़े की संख्या) के माप के रूप में व्युत्क्रमों की गिनती का उपयोग करना i और j साथ i < j और A[i] > A[j]; यादृच्छिक रूप से क्रमबद्ध इनपुट के लिए यह लगभग है n2/4), के साथ संभावित इनपुट अनुक्रम हैं O(n log n) व्युत्क्रम जो इसे लेने का कारण बनते हैं Ω(n log n) समय, जबकि अन्य अनुकूली सॉर्ट एल्गोरिदम इन मामलों को हल कर सकते हैं O(n log log n) समय।[2] स्मूथसॉर्ट एल्गोरिदम को लियोनार्डो ढेर के सभी पेड़ों के आकार को स्मृति में रखने में सक्षम होना चाहिए। चूँकि उन्हें क्रम के अनुसार क्रमबद्ध किया जाता है और सभी ऑर्डर अलग-अलग होते हैं, यह आमतौर पर बिट वेक्टर का उपयोग करके किया जाता है जो दर्शाता है कि कौन से ऑर्डर मौजूद हैं। इसके अलावा, चूँकि सबसे बड़ा ऑर्डर अधिकतम है O(log n), इन बिट्स को एन्कोड किया जा सकता है O(1) मशीन शब्द, एक ट्रांसडिकोटोमस मशीन मॉडल मानते हुए।
ध्यान दें कि O(1) मशीनी शब्द एक मशीनी शब्द के समान नहीं हैं। एक 32-बिट वेक्टर केवल इससे कम आकार के लिए पर्याप्त होगा L(32) = 7049155. एक 64-बिट वेक्टर इससे कम आकार के लिए उपयुक्त होगा L(64) = 34335360355129 ≈ 245. सामान्य तौर पर, इसमें लगता है 1/log2(φ) ≈ 1.44 आकार के प्रति बिट वेक्टर के बिट्स।
चिनार प्रकार
स्मूथसॉर्ट से प्रेरित एक सरल एल्गोरिदम पॉपलर सॉर्ट है।[5] डच पोल्डरों में अक्सर देखे जाने वाले घटते आकार के पेड़ों की पंक्तियों के नाम पर, यह उन इनपुटों के लिए स्मूथसॉर्ट की तुलना में कम तुलना करता है जो अधिकतर सॉर्ट नहीं किए जाते हैं, लेकिन सॉर्ट किए गए इनपुट के लिए रैखिक समय प्राप्त नहीं कर सकते हैं।
चिनार की छंटाई द्वारा किया गया महत्वपूर्ण परिवर्तन यह है कि विभिन्न पेड़ों की जड़ों को क्रमबद्ध क्रम में नहीं रखा जाता है; उन्हें एक ही ढेर में बांधने वाली कोई सौतेली कड़ियाँ नहीं हैं। इसके बजाय, हर बार जब दूसरे चरण में ढेर सिकुड़ जाता है, तो अधिकतम प्रविष्टि खोजने के लिए जड़ों की खोज की जाती है।
क्योंकि वहाँ हैं n सिकुड़ते चरण, जिनमें से प्रत्येक को खोजना होगा O(log n) अधिकतम के लिए पेड़ की जड़ें, चिनार की किस्म के लिए सबसे अच्छा रन टाइम है O(n log n).
लेखक आगे सरलीकरण प्रदान करने के लिए लियोनार्डो पेड़ों के बजाय सही बाइनरी पेड़ों का उपयोग करने का भी सुझाव देते हैं, लेकिन यह एक कम महत्वपूर्ण परिवर्तन है।
उसी संरचना को पोस्ट-ऑर्डर हीप नाम के तहत सामान्य प्रयोजन प्राथमिकता कतार के रूप में प्रस्तावित किया गया है,[6] को प्राप्त करने O(1) एक अंतर्निहित द्विपद ढेर की तुलना में सरल संरचना में परिशोधित विश्लेषण प्रविष्टि समय।
अनुप्रयोग
माँसपेशियाँ सी लाइब्रेरी इसके कार्यान्वयन के लिए स्मूथसॉर्ट का उपयोग करती है qsort().[7][8]
संदर्भ
- ↑ 1.0 1.1 Dijkstra, Edsger W. 16 Aug 1981 (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.
One can also raise the question why I have not chosen as available stretch lengths: ... 63 31 15 7 3 1 which seems attractive since each stretch can then be viewed as the postorder traversal of a balanced binary tree. In addition, the recurrence relation would be simpler. But I know why I chose the Leonardo numbers:
(transcription) - ↑ 2.0 2.1 2.2 Hertel, Stefan (13 May 1983). "Smoothsort's behavior on presorted sequences" (PDF). Information Processing Letters. 16 (4): 165–170. doi:10.1016/0020-0190(83)90116-3.
- ↑ Brown, Craig (21 Jan 2013). "Fastest In-Place Stable Sort". Code Project.[self-published source]
- ↑ Eisenstat, David (13 September 2020). "Where is the smoothsort algorithm used?". Stack Overflow. Retrieved 2020-10-28.
Smoothsort is not stable, and stability is often more desirable than in-place in practice
- ↑ Bron, Coenraad; Hesselink, Wim H. (13 September 1991). "Smoothsort revisited". Information Processing Letters. 39 (5): 269–276. doi:10.1016/0020-0190(91)90027-F.
- ↑ Harvey, Nicholas J. A.; Zatloukal, Kevin (26–28 May 2004). The Post-Order Heap. Third International Conference on Fun with Algorithms (FUN 2004). Elba, Italy.
- ↑ Felker, Rich (30 April 2013). "How do different languages implement sorting in their standard libraries?". Stack Overflow. Retrieved 2020-10-28.
- ↑ Ochs, Valentin; Felker, Rich (11 August 2017). "src/stdlib/qsort.c". musl - an implementation of the standard library for Linux-based systems. Retrieved 2021-01-26.
बाहरी संबंध
- Commented transcription of EWD796a, 16-Aug-1981
- Detailed modern explanation of Smoothsort
- wikibooks:Algorithm Implementation/Sorting/Smoothsort
- Description and example implementation of Poplar heap
- Noshita, Kohei; Nakatani, Yoshinobu (April 1985). "On the Nested Heap Structure in Smoothsort". Mathematical Foundations of Computer Science and Their Applications (Japanese: 数理解析研究所講究録) (in English). 556: 1–16.
