स्मूथसॉर्ट: Difference between revisions
(Created page with "{{Short description|Comparison-based sorting algorithm}} {{Infobox Algorithm |class=Sorting algorithm |image=File:Smoothsort.gif||alt=An animation depicting smoothsort's...") |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
|class=[[Sorting algorithm]] | |class=[[Sorting algorithm]] | ||
|image=[[File:Smoothsort.gif||alt=An animation depicting smoothsort's operation, showing the heap being built and then disassembled,]] | |image=[[File:Smoothsort.gif||alt=An animation depicting smoothsort's operation, showing the heap being built and then disassembled,]] | ||
|caption= | |caption=स्मूथसॉर्ट एक ऐसे एरे पर कार्य करता है जो अधिकांश आदेश में होता है। ऊपर की बार ट्री संरचना दर्शाती है। | ||
|data=[[Array data structure|Array]] | |data=[[Array data structure|Array]] | ||
|time={{math|''O''(''n'' log ''n'')}} | |time={{math|''O''(''n'' log ''n'')}} | ||
| Line 12: | Line 12: | ||
}} | }} | ||
[[कंप्यूटर विज्ञान]] में, स्मूथसॉर्ट एक | |||
[[कंप्यूटर विज्ञान]] में, '''स्मूथसॉर्ट''' एक तुलना-आधारित क्रमबद्ध करने वाला एल्गोरिदम है। हीपसॉर्ट का एक वेरिएंट होता है, जिसे 1981 में [[एडवर्ड डिज्क्स्ट्रा]] ने आविष्कार और प्रकाशित किया था।<ref name="EWD-796a">{{Cite EWD|796a|16 Aug 1981|Smoothsort – an alternative to sorting in situ|quote=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:}}</ref> स्मूथसॉर्ट भी हीपसॉर्ट की तरह एक स्थानीय एल्गोरिदम है जिसका अपर सीमा {{math|''[[Big O notation|O]]''(''n'' log ''n'')}},{{r|hertel}} होता है, परंतु यह [[स्थिर प्रकार|स्थिर क्रमबद्ध]] करने वाला नहीं है।<ref>{{cite web | |||
|title=Fastest In-Place Stable Sort | |title=Fastest In-Place Stable Sort | ||
|first=Craig |last=Brown | |first=Craig |last=Brown | ||
| Line 18: | Line 19: | ||
|url=http://www.codeproject.com/Articles/26048/Fastest-In-Place-Stable-Sort | |url=http://www.codeproject.com/Articles/26048/Fastest-In-Place-Stable-Sort | ||
|publisher=[[Code Project]] | |publisher=[[Code Project]] | ||
}}{{self-published source|date=January 2016}}</ref> | }}{{self-published source|date=January 2016}}</ref><ref>{{cite web | ||
|title=Where is the smoothsort algorithm used? | |title=Where is the smoothsort algorithm used? | ||
|first=David |last=Eisenstat | |first=David |last=Eisenstat | ||
| Line 26: | Line 27: | ||
|access-date=2020-10-28 | |access-date=2020-10-28 | ||
|quote=Smoothsort is not stable, and stability is often more desirable than in-place in practice | |quote=Smoothsort is not stable, and stability is often more desirable than in-place in practice | ||
}}</ref> स्मूथसॉर्ट का लाभ यह है कि यह | }}</ref> स्मूथसॉर्ट का लाभ यह है कि यदि प्रारंभिक रूप से सॉर्टेड होने वाली इनपुट हो, तो यह {{math|''O''(''n'')}} समय के पास आता है, जबकि हीपसॉर्ट का औसत {{math|''O''(''n'' log ''n'')}} होता है, चाहे आदि सॉर्ट हो या न हो। | ||
==अवलोकन== | ==अवलोकन== | ||
स्मूथसॉर्ट भी हीपसॉर्ट की तरह इनपुट को एक [[प्राथमिकता कतार]] (प्रायोरिटी कतार) में संगठित करता है और पुनः बार-बार अधिकतम को निकालता है। हीपसॉर्ट की तरह हीपसॉर्ट के लिए प्राथमिकता कतार एक निहित हीप डेटा संरचना (एक हीप-क्रमित निहित [[ द्विआधारी वृक्ष |द्विआधारी वृक्ष]] ) होती है, जो सरणी का एक प्रीफिक्स (प्राथमिकता कतार की संक्षेप में) में स्थान रोकती है। प्रत्येक निकालने से प्रीफिक्स न्यूनतम हो जाता है और निकाले गए तत्व को एक बढ़ती हुई क्रमबद्ध साफ़ समाप्ति में जोड़ता है। जब प्रीफिक्स को शून्य न्यूनतम हो जाता है, तो सरणी पूरी तरह से क्रमबद्ध हो जाती है। | |||
हीपसॉर्ट | हीपसॉर्ट बाइनरी [[ द्विआधारी वृक्ष |वृक्ष]] को सरणी में मानचित्र करता है जहां वृक्ष का ऊपर से नीचे ब्रेड्थ-फर्स्ट ट्रेवर्सल का उपयोग किया जाता है। सरणी में पहले मूल तत्व आता है, पुनः उसके दो बच्चे, पुनः चार पोते, और ऐसे ही आगे भी होते हैं। हर तत्व का जड़ से मान निर्धारित होता है वृक्ष की जड़ से नीचे के गहराई में, और मूल तत्व को छोड़कर हर तत्व की संदर्भ सरणी में पिछले तत्व के पश्चात आती है। यद्यपि, पत्तियों से ऊपर उठने की ऊंचाई सरणी के आकार पर निर्भर करती है। इसका दोष यह है कि क्रमबद्ध करने की प्रक्रिया के हिस्से के रूप में हर तत्व को ले जाना होता है: इसे अंतिम स्थान पर ले जाने से पहले यह मूल तत्व के माध्यम से गुजरना होता है। | ||
स्मूथसॉर्ट एक | स्मूथसॉर्ट एक विभिन्न मानचित्रण का उपयोग करता है, जो एक नीचे से ऊपर की गहराई में पोस्ट-आर्डर ट्रेवर्सल होता है। एक बाएं बच्चा अपने भाई पर आधारित उपवृक्ष के उपरांत आता है, और एक दाएं बच्चा अपने माता-पिता के उपरांत आता है। हर तत्व की पत्तियों से ऊपर की गहराई में एक निर्धारित ऊंचाई होती है, और हर गैर-पत्ती तत्व के बच्चे सरणी में पिछले होते हैं। यद्यपि, जड़ रूट के नीचे की गहराई सरणी के आकार पर निर्भर करती है। एल्गोरिदम को ऐसे संगठित किया जाता है कि रूट हीप के अंत में होती है, और जब हीप से तत्व निकाला जाता है, तो वह पहले से ही अपने अंतिम स्थान पर होता है और इसे हटाने की आवश्यकता नहीं होती है। इसके अलावा, एक क्रमबद्ध सरणी पहले से ही एक मान्य हीप है, और कई क्रमबद्ध अंतराल मान्य हीप-क्रमित उपवृक्ष होते हैं। | ||
औपचारिक रूप से कहें तो, हर स्थान i एक अद्वितीय उपवृक्ष की जड़ होता है, जिसके नोड i तक की एक संयुक्त अवधि को धारण करते हैं। सरणी का एक प्रारंभिक प्रीफिक्स (संपूर्ण सरणी सहित), एक ऐसी अवधि हो सकती है जो किसी उपवृक्ष के लिए एक उपवृक्ष अवधि के संयोजन के रूप में होती है, परंतु सामान्य रूप से इसे कई निरंतर उपवृक्ष अवधियों के एक संयोजन के रूप में विघटित किया जाता है, जिन्हें डाइजक्स्ट्रा "स्ट्रेच" कहते हैं। किसी माता-पिता के बिना कोई भी उपवृक्ष (अर्थात् पथरूप में निर्धारित स्थान की जड़ से निर्मित) प्रारंभिक प्रीफिक्स के विघटन में एक स्ट्रेच देता है, जिसके कारण यह विघटन अद्वितीय होता है। जब प्रीफिक्स में एक नवीन नोड जोड़ा जाता है, तो दो स्थितियाँ हो सकती हैं: या वह स्थान एक पत्ती होता है और विघटन में एक लंबाई 1 का स्ट्रेच जोड़ता है, या वह आखिरी दो स्ट्रेच के साथ मिलकर, उनके संबंधित जड़ों के माता-पिता बनकर, इस प्रकार उन्हें दो स्ट्रेचों को एक नवीन स्ट्रेच के रूप में परिवर्तित करता है, जिसमें उनके संयोजन का संयोजन और नया (रूट) स्थान समावेश होता है। | |||
डाइजक्स्ट्रा ने दर्शाया{{r|EWD-796a}} कि स्पष्ट नियम होगा कि स्ट्रेच केवल तभी मिलाए जाएंगे जब उनका आकार समान हो, जिसके परिणामस्वरूप सभी उपवृक्ष पूर्ण द्विआधारी वृक्ष होंगे जिनका आकार {{math|2<sup>''k''</sup>−1}} होता है। यद्यपि, उन्होंने एक पृथक नियम चुना है, जिससे अधिक संभावित वृक्ष आकार मिलते हैं। इसमें असिम्प्टोटिक दक्षता में कोई परिवर्तित नहीं होता है,{{r|hertel}} परंतु प्रत्येक अवधि को कवर करने के लिए न्यूनतम संख्या में स्ट्रेच की आवश्यकता होने के कारण, यह दक्षता में छोटे संख्यात्मक कारक का लाभ प्राप्त करता है। | |||
डिज्क्स्ट्रा जिस नियम का उपयोग करता है वह यह है कि अंतिम दो हिस्सों को संयोजित किया जाता है यदि और केवल तभी जब उनका आकार | डिज्क्स्ट्रा जिस नियम का उपयोग करता है वह यह है कि अंतिम दो हिस्सों को संयोजित किया जाता है यदि और केवल तभी जब उनका आकार निरंतर [[लियोनार्डो संख्या]] हो {{math|''L''(''i''+1)}} और {{math|''L''(''i'')}} (उस क्रम में), किन संख्याओं को पुनरावर्ती रूप से परिभाषित किया गया है, [[फाइबोनैचि संख्या]]ओं के समान ही है, जैसे: | ||
* {{math|1=''L''(0) = ''L''(1) = 1}} | * {{math|1=''L''(0) = ''L''(1) = 1}} | ||
* {{math|1=''L''(''k''+2) = ''L''(''k''+1) + ''L''(''k'') + 1}} | * {{math|1=''L''(''k''+2) = ''L''(''k''+1) + ''L''(''k'') + 1}} | ||
परिणामस्वरूप, किसी भी उपवृक्ष का आकार लियोनार्डो संख्या है। खिंचाव के आकार का क्रम पहले विघटित होता है {{mvar|n}}पद, किसी के लिए {{mvar|n}}, लालची | परिणामस्वरूप, किसी भी उपवृक्ष का आकार लियोनार्डो संख्या है। खिंचाव के आकार का क्रम पहले विघटित होता है {{mvar|n}}पद, किसी के लिए {{mvar|n}}, लालची विधियों से पाया जा सकता है: पहला आकार सबसे बड़ा लियोनार्डो संख्या से अधिक नहीं है {{mvar|n}}, और शेष (यदि कोई हो) पुनरावर्ती रूप से विघटित हो जाता है। स्ट्रेच के आकार न्यूनतम हो रहे हैं, संभवतः दो अंतिम आकार 1 को छोड़कर, और संभवतः अंतिम दो आकारों को छोड़कर क्रमिक लियोनार्डो संख्याओं से परहेज किया जा रहा है। | ||
इस परिणामस्वरूप, किसी भी उपवृक्ष का आकार एक लियोनार्डो संख्या होता है। किसी भी nपद के लिए, प्रथम nपद स्थानों को विघटित करने वाली स्ट्रेचों के आकार का अनुक्रम लोभी विधियों से प्राप्त किया जा सकता है: पहला आकार n पद से छोटा लियोनार्डो संख्या है, और शेषांश (यदि कोई हो) को पुनर्निर्भर रूप से विघटित किया जाता है। स्ट्रेचों के आकार घटते हैं, सख्त रूप से केवल दो अंतिम आकार 1 के लिए छोड़ते हैं, और यह सुनिश्चित करते हैं कि दो आकारों के पड़ोसी लियोनार्डो संख्याओं के अतिरिक्त कोई लगातार संख्याएं नहीं होती हैं, केवल शेष दो आकारों के लिए ऐसा हो सकता है। | |||
हर स्ट्रेच एक हीप-आदेशित वृक्ष होने के अतिरिक्त, वृक्षों के रूट सॉर्टेड क्रम में रखे जाते हैं। इसके परिणामस्वरूप, प्रत्येक रूट के पश्चिमी रूट से जुड़ने के लिए एक तीसरा बच्चा (जिसे डाइजक्स्ट्रा "स्टेपसन" कहते हैं) जोड़ा जाता है। इससे सभी वृक्षों को साथ मिलाकर एक समूचे वैश्विक हीप में मिलाया जाता है, जिसमें वैश्विक अधिकतम अंतिम में स्थित होता है। | |||
यद्यपि, प्रत्येक नोड के स्टेपसन का स्थान स्थिर होता है, परंतु यह संपर्क केवल वृक्ष की जड़ों के लिए होता है, इसका अर्थ है कि जब वृक्षों को मिलाया जाता है, तब संपर्क हटा दिया जाता है। यह साधारित बच्चों से पृथक है, जो तब तक संपर्क में होते हैं जब तक माता-पिता उपस्थित होता हैं। | |||
सॉर्टिंग की पहली (हीप बढ़ाने वाली) चरण में, एक बढ़ते हुए विस्तार के साथ एक प्रारंभिक हिस्सा को पुनर्व्यवस्थित किया जाता है क्योंकी प्रत्येक स्ट्रेच के लिए उसके उपवृक्ष हीप हो: किसी भी गैर-पत्ता स्थिति में, किसी भी गैर-पत्ता स्थिति पर विद्यमान प्रवेश न्यूनतम से न्यूनतम उसके बच्चों की स्थितियों के प्रवेश से न्यूनतम होता है। इसके अतिरिक्त, सभी रूट्स उनके स्टेपसन्स से न्यूनतम से न्यूनतम होते हैं। | |||
व्यावहारिक कार्यान्वयन | दूसरे चरण में, अधिकतम नोड को सरणी के अंत से पृथक कर दिया जाता है, और ढेर अपरिवर्तनीय को उसके बच्चों के मध्य पुनः से स्थापित किया जाता है। | ||
व्यावहारिक कार्यान्वयन में प्रायः लियोनार्डो संख्याओं {{math|''L''(''k'')}} की गणना की जरूरत होती है। डाइजक्स्ट्रा ने चतुर कोड प्रदान किया है जिसमें एक स्थायी संख्या चरोंवाले पूर्णांकीय मानों का उपयोग करके आवश्यक मानों की प्रभावी गणना की जाती है। वैकल्पिक रूप से, यदि सॉर्ट करने के लिए एरे का आकार {{mvar|N}} का एक सीमित बाउंड होता है, तो {{math|''O''(log ''N'')}} अंतरिक्ष में पूर्व-गणित लियोनार्डो संख्या की एक पूर्वनिर्धारित सारणी संग्रहीत की जा सकती है। | |||
==संचालन== | ==संचालन== | ||
जब श्रेणी-ऑफ-हीप संरचना के विकास की दृष्टि से तकनीकी क्रिया के दो चरण एक-दूसरे के विपरीत होते हैं, तब वे एक मूल साधन का उपयोग करके कार्यान्वित किए जाते हैं, जो एक बाइनरी मैक्स-हीप में "सिफ्ट डाउन" आपरेशन के समकक्ष है। | |||
===छानना === | ===छानना === | ||
मूल सिफ्ट-डाउन आपरेशन उस समय हीप अवियोग संरचना को पुनः स्थापित करता है जब इसका संभवतः केवल मूल तत्व नोड पर उल्लंघन किया जाता है। यदि मूल तत्व नोड अपने किसी भी बच्चे से न्यूनतम है, तो इसे उसके सबसे बड़े बच्चे के साथ परिवर्तित करता दिया जाता है और प्रक्रिया को उसके नए उपवृक्ष में मूल तत्व नोड के साथ दोहराया जाता है। | |||
स्मूथसॉर्ट और बाइनरी मैक्स-हीप के | स्मूथसॉर्ट और एक बाइनरी मैक्स-हीप के मध्य अंतर यह है कि प्रत्येक स्ट्रेच की रूट को तीसरे "स्टेपसन" के संबंध में क्रमबद्ध किया जाना चाहिए: पिछले स्ट्रेच की रूट। इसलिए, सिफ्ट-डाउन प्रक्रिया चार-तरफी तुलनाएं के साथ प्रारंभ होती है जब तक स्टेपसन अधिकतम तत्व नहीं होता है, और पुनः तीन-तरफी तुलनाएं के साथ जब तक रूट नोड अपना अंतिम गृह नहीं मिलता है और नियम स्थापित किए जाते हैं। | ||
प्रत्येक | प्रत्येक वृक्ष पूर्ण बाइनरी वृक्ष है: प्रत्येक नोड के दो बच्चे होते हैं या कोई नहीं होते। साधारित निहित बाइनरी हीप में जो एक बच्चा होता है, उसे संबोधित करने की कोई आवश्यकता नहीं होती है। | ||
क्योंकि | क्योंकि यहाँ {{math|''O''(log ''n'')}} असंख्य स्ट्रेचेस हैं, जिनमें प्रत्येक एक वृक्ष {{math|''O''(log ''n'')}} की गहराई का होता है, इसलिए प्रत्येक सिफ्ट-डाउन आपरेशन को करने का समय {{math|''O''(log ''n'')}} से बंधा हुआ है। | ||
===दाईं ओर एक तत्व को | ===दाईं ओर एक तत्व को सम्मलित करके ढेर क्षेत्र को बढ़ाना=== | ||
जब एक अतिरिक्त तत्व को स्ट्रेच के अनुक्रम | जब एक अतिरिक्त तत्व को स्ट्रेच के अनुक्रम में सम्मलित करने पर विचार किया जाता है, तो यह या तो एक नया एक-तत्व स्ट्रेच बनाता है, या यह दोनों जड़ों के माता-पिता बनकर दो सबसे दाहिने स्ट्रेच को जोड़ता है और एक नया स्ट्रेच बनाता है। जो क्रम में दोनों को प्रतिस्थापित करता है। दोनों में से क्या होता है यह केवल वर्तमान में उपस्थित हिस्सों के आकार पर निर्भर करता है ,डाइक्स्ट्रा ने निर्धारित किया कि स्ट्रेच केवल तभी जोड़े जाएंगे जब उनके आकार {{math|''L''(''k''+1)}} और {{math|''L''(''k'')}} हों, अर्थात, क्रमशः लियोनार्डो नंबर्स; नया स्ट्रेच आकार {{math|''L''(''k''+2)}}.होगा। | ||
दोनों यद्यपि, नए तत्व को आपको सही स्थान पर नीचे स्थानांतरित करना होता है। यदि नया नोड एक-तत्व स्ट्रेच है, तो उसे फिर भी पिछले स्ट्रेच के रूट के संबंध में क्रमबद्ध किया जाना चाहिए। | |||
====अनुकूलन==== | ====अनुकूलन==== | ||
डाइक्स्ट्रा का एल्गोरिदम काम बचाने के लिए यह देखते हैं कि सम्पूर्ण हीप अनुपात तब आवश्यक है जब वृद्धि चरण के अंत में होता है, लेपरंतु प्रत्येक मध्यवर्ती चरण में यह आवश्यक नहीं होती है। विशेष रूप से, एक तत्व अपने स्टेपसन से अधिक होने की आवश्यकता केवल वे तत्वों के लिए है जो अंतिम वृक्ष मूल होती हैं। | |||
इसलिए, जब | इसलिए, जब एक तत्व जोड़ा जाता है, तो इसके भविष्य के माता-पिता की स्थिति को निर्धारित करते है। यदि यह बचे हुए मान्यों के सृजन के सीमा के अंदर है, तो ऐसा लगाएं जैसे कि कोई स्टेपसन नहीं है और केवल वर्तमान पेड़ में सिर्फ नीचे के लिए छानकर ही कार्य किया जाना चाहिए। | ||
===सबसे दाहिने तत्व को | ===सबसे दाहिने तत्व को पृथक करके ढेर क्षेत्र को छोटा करना=== | ||
इस चरण के दौरान, | इस चरण के दौरान, स्ट्रेचों की अनुक्रमणिका का रूप वृद्धि चरण के परिवर्तित रूप से परिवर्तित होता है। एक पत्ती नोड को पृथक करते समय किसी भी काम की आवश्यकता नहीं होती है, परंतु एक गैर-पत्ती नोड के लिए इसके दो बच्चे नए हिस्सों की जड़ें बन जाते हैं, और हिस्सों की जड़ों के क्रम में उन्हें उनके उचित स्थान पर ले जाने की आवश्यकता होती है। इसे दो बार सिफ्ट-डाउन लागू करके प्राप्त किया जा सकता है: पहले बाएं बच्चे के लिए, और पुनः दाएं बच्चे के लिए था। | ||
क्योंकि | क्योंकि पूर्ण द्विआधारिक वृक्ष में आधी संख्या के सभी नोड पत्ते होते हैं, इससे प्रति नोड औसतन एक सिफ्ट-डाउन ऑपरेशन कार्यान्वित होता है। | ||
====अनुकूलन==== | ====अनुकूलन==== | ||
पहली बार सिफ्ट-डाउन करते समय, नए उज्ज्वलित रूट्स सामान्य बच्चों के संबंध में सही क्रम में होते हैं; इसके अलावा, केवल उनके स्टेपसन्स के संबंध में क्रम विचार में है। इसलिए, हीप को छोटा करते समय, सिफ्ट-डाउन के पहले कदम को स्टेपसन के साथ एकल तुलना के रूप में सरलित किया जा सकता है। यदि स्वैप होता है, तो आगामी कदम पूर्ण चार तरह की तुलना करनी होगी। | |||
==विश्लेषण== | ==विश्लेषण== | ||
स्मूथसॉर्ट | स्मूथसॉर्ट एक प्रस्तुत अर्र्य संख्यापटल में {{math|''O''(''n'')}}समय लेता है, सबसे खराब मामले में {{math|''O''(''n'' log ''n'')}} और लगभग सम्भावित रूप से लीनियर प्रदर्शन करता है। यद्यपि, यह सभी लगभग संविधानिक अनुक्रमों को आदर्श ढंग से नहीं संभालता है। जब अव्यवस्थितता के माप के रूप में इनवर्सन की गिनती का उपयोग किया जाता है (इंडेक्स{{mvar|i}} और {{mvar|j}} साथ {{math|''i'' < ''j''}} और {{math|''A''[''i''] > ''A''[''j'']}} के जोड़े की संख्या; यादृच्छिक रूप से छांटे गए इनपुट के लिए इसका लगभग n2/4 होता है), तो ऐसे संभव इनपुट सरणियों में {{math|''O''(''n'' log ''n'')}} इनवर्सन हो सकते हैं जो इसे {{math|Ω(''n'' log ''n'')}} समय लेने का कारण बनाते हैं, जबकि अन्य एडेप्टिव सॉर्टिंग एल्गोरिदम {{math|''O''(''n'' log log ''n'')}} समय में इन परिस्थितियों को हल कर सकते हैं।<ref name="hertel">{{cite journal | ||
|last=Hertel |first=Stefan | |last=Hertel |first=Stefan | ||
|title=Smoothsort's behavior on presorted sequences | |title=Smoothsort's behavior on presorted sequences | ||
| Line 94: | Line 95: | ||
|doi=10.1016/0020-0190(83)90116-3 | |doi=10.1016/0020-0190(83)90116-3 | ||
}}</ref> | }}</ref> | ||
ध्यान दें कि {{math|''O''(1)}} | स्मूथसॉर्ट एल्गोरिदम को सभी लियोनार्डो हीप के सभी पेड़ों के आकारों को मेमोरी में रखने की आवश्यकता होती है। क्योंकि वे आदेश के अनुसार क्रमबद्ध हैं और सभी आदेश अलग हैं, इसे सामान्यतः उपस्थित होने वाले आदेश की इंद्रिय वेक्टर का उपयोग करके किया जाता है। इसके अलावा, क्योंकि सबसे बड़े आदेश का अधिकतम {{math|''O''(log ''n'')}} होता है, इन बिट्स को {{math|''O''(1)}} मशीन शब्दों में एनकोड किया जा सकता है, यह अनुमानित करता है एक [[ट्रांसडिकोटोमस मशीन मॉडल|ट्रांसडिकोटोमस]] [[ट्रांसडिकोटोमस मशीन मॉडल|मशीन मॉडल]] का अनुमान किया जाता है। | ||
ध्यान दें कि {{math|''O''(1)}} मशीन शब्दों का अर्थ एक मशीन शब्द से अलग चीज़ नहीं है। एक 32-बिट वेक्टर केवल {{math|1=''L''(32) = 7049155}} से न्यूनतम आकार के लिए पर्याप्त होगा। {{math|1=''L''(64) = 34335360355129 ≈ 2<sup>45</sup>}}से न्यूनतम आकार के लिए एक 64-बिट वेक्टर कारगर होगा। सामान्यतः, प्रति आकार के {{math|1/log<sub>2</sub>(''[[Golden ratio|φ]]'') ≈ 1.44}} बिट वेक्टर प्रति बिट की जगह चाहिए। | |||
==चिनार प्रकार== | ==चिनार प्रकार== | ||
स्मूथसॉर्ट से प्रेरित एक सरल एल्गोरिदम | |||
पॉपलर सॉर्ट, स्मूथसॉर्ट से प्रेरित एक सरल एल्गोरिदम है।<ref>{{cite journal | |||
|title=Smoothsort revisited | |title=Smoothsort revisited | ||
|first1=Coenraad |last=Bron |author-link1=Coenraad Bron | |first1=Coenraad |last=Bron |author-link1=Coenraad Bron | ||
| Line 106: | Line 110: | ||
|volume=39 |issue=5 |pages=269–276 |date=13 September 1991 | |volume=39 |issue=5 |pages=269–276 |date=13 September 1991 | ||
|doi=10.1016/0020-0190(91)90027-F | |doi=10.1016/0020-0190(91)90027-F | ||
}}</ref> डच [[पोल्डर]] | }}</ref> डच [[पोल्डर]] में देखे जाने वाले न्यूनतम होने वाले आकार के पेड़ की पंक्तियों के नाम पर रखा गया है। यह स्मूथसॉर्ट की तुलना में न्यूनतम तुलनाएं करता है जब इनपुट अधिकांश रूप से सॉर्ट नहीं होता है, परंतु सॉर्ट किए गए इनपुट के लिए रैखिक समय प्राप्त नहीं कर सकते हैं। | ||
पॉपलर सॉर्ट में महत्वपूर्ण परिवर्तन है कि विभिन्न पेड़ों की जड़ों को क्रमबद्ध क्रम में नहीं रखा जाता है; उन्हें एक हीप में बांधने वाले "स्टेपसन" लिंक नहीं होते हैं। इसके अतिरिक्त, जब भी दूसरे चरण में हीप को छोटा किया जाता है, रूट्स को खोजने के लिए अधिकतम प्रविष्टि ढूंढी जाती है।. | |||
पॉपलर सॉर्ट का सर्वोत्तम मामला रनटाइम {{math|''O''(''n'' log ''n'')}} होता है, क्योंकि इसमें n छोटने के चरण होते हैं, जिनमें से प्रत्येक में अधिकतम के लिए {{math|''O''(log ''n'')}} पेड़ की जड़ें की खोज करनी होती है। | |||
लेखकों ने यह भी सुझाव दिया है कि और सरलीकरण के लिए लियोनार्डो पेड़ों की अतिरिक्त सही बाइनरी पेड़ों का उपयोग किया जाए, परंतु यह एक न्यूनतम महत्वपूर्ण परिवर्तन है। | |||
उसी संरचना को पोस्ट-ऑर्डर हीप नाम के तहत सामान्य प्रयोजन प्राथमिकता कतार के रूप में प्रस्तावित किया गया है,<ref>{{cite conference | उसी संरचना को पोस्ट-ऑर्डर हीप नाम के तहत सामान्य प्रयोजन प्राथमिकता कतार के रूप में प्रस्तावित किया गया है, को प्राप्त करने एक अंतर्निहित [[द्विपद ढेर]] की तुलना में सरल संरचना में परिशोधित विश्लेषण प्रविष्टि समय। | ||
एक ही संरचना को सामान्य उद्देश्यों के लिए पोस्ट-ऑर्डर हीप के रूप में प्रस्तावित किया गया है<ref>{{cite conference | |||
|title=The Post-Order Heap | |title=The Post-Order Heap | ||
|first1=Nicholas J. A. |last1=Harvey |first2=Kevin |last2=Zatloukal | |first1=Nicholas J. A. |last1=Harvey |first2=Kevin |last2=Zatloukal | ||
| Line 120: | Line 126: | ||
|conference=Third International Conference on Fun with Algorithms (FUN 2004) | |conference=Third International Conference on Fun with Algorithms (FUN 2004) | ||
|location=[[Elba]], Italy |date=26–28 May 2004 | |location=[[Elba]], Italy |date=26–28 May 2004 | ||
}}</ref> | }}</ref>, जो एक अंतर्निहित [[द्विपद ढेर|द्विपद हीप]] से भी सरल होने के साथ {{math|''O''(1)}} अमोर्टिज़ेशन निम्नतम समय में संघटित करने की प्राप्ति करती है। | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
सी लाइब्रेरी इसके कार्यान्वयन के लिए स्मूथसॉर्ट का उपयोग करती है . | |||
[[माँसपेशियाँ|मस्ल सी]] लाइब्रेरी <code>[[qsort]]()</code> के अपने अभिन्यास के लिए स्मूथसॉर्ट का उपयोग करती है।<ref>{{cite web | |||
|title=How do different languages implement sorting in their standard libraries? | |title=How do different languages implement sorting in their standard libraries? | ||
|url=https://stackoverflow.com/questions/16308374/how-do-different-languages-implement-sorting-in-their-standard-libraries/16309486#16309486 | |url=https://stackoverflow.com/questions/16308374/how-do-different-languages-implement-sorting-in-their-standard-libraries/16309486#16309486 | ||
| Line 136: | Line 144: | ||
|url=https://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c | |url=https://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c | ||
}}</ref> | }}</ref> | ||
| Line 143: | Line 152: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [https://www.enterag.ch/hartwig/order/smoothsort.pdf | * [https://www.enterag.ch/hartwig/order/smoothsort.pdf Commenपदted tranपदscriptionपदof EWD796a, 16-Aug-1981] | ||
* [https://www.keithschwarz.com/smoothsort/ Detailed | * [https://www.keithschwarz.com/smoothsort/ Detailed modernपदexplanपदationपदof Smoothsort] | ||
* [[wikibooks:Algorithm Implementation/Sorting/Smoothsort]] | * [[wikibooks:Algorithm Implementation/Sorting/Smoothsort|wikibooks:Algorithm Implemenपदtationपद/Sortinपदg/Smoothsort]] | ||
* [https://github.com/Morwenn/poplar-heap | * [https://github.com/Morwenn/poplar-heap Descriptionपदanपदd example implemenपदtationपदof Poplar heap] | ||
* {{cite journal | * {{cite journal | ||
|title=On the Nested Heap Structure in Smoothsort | |title=On the Nested Heap Structure in Smoothsort | ||
| Line 155: | Line 164: | ||
}} | }} | ||
{{sorting}} | {{sorting}} | ||
[[Category: | [[Category:Accuracy disputes from January 2016]] | ||
[[Category:All accuracy disputes]] | |||
[[Category:Articles containing Japanese-language text]] | |||
[[Category:Articles with invalid date parameter in template]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:Collapse templates]] | |||
[[Category:Created On 27/06/2023]] | [[Category:Created On 27/06/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:एड्सगर डब्ल्यू डिज्क्स्ट्रा]] | |||
[[Category:छँटाई एल्गोरिदम]] | |||
[[Category:ढेर (डेटा संरचनाएं)]] | |||
[[Category:तुलना प्रकार]] | |||
Latest revision as of 17:49, 16 July 2023
 स्मूथसॉर्ट एक ऐसे एरे पर कार्य करता है जो अधिकांश आदेश में होता है। ऊपर की बार ट्री संरचना दर्शाती है। | |
| 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][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 को छोड़कर, और संभवतः अंतिम दो आकारों को छोड़कर क्रमिक लियोनार्डो संख्याओं से परहेज किया जा रहा है।
इस परिणामस्वरूप, किसी भी उपवृक्ष का आकार एक लियोनार्डो संख्या होता है। किसी भी nपद के लिए, प्रथम nपद स्थानों को विघटित करने वाली स्ट्रेचों के आकार का अनुक्रम लोभी विधियों से प्राप्त किया जा सकता है: पहला आकार n पद से छोटा लियोनार्डो संख्या है, और शेषांश (यदि कोई हो) को पुनर्निर्भर रूप से विघटित किया जाता है। स्ट्रेचों के आकार घटते हैं, सख्त रूप से केवल दो अंतिम आकार 1 के लिए छोड़ते हैं, और यह सुनिश्चित करते हैं कि दो आकारों के पड़ोसी लियोनार्डो संख्याओं के अतिरिक्त कोई लगातार संख्याएं नहीं होती हैं, केवल शेष दो आकारों के लिए ऐसा हो सकता है।
हर स्ट्रेच एक हीप-आदेशित वृक्ष होने के अतिरिक्त, वृक्षों के रूट सॉर्टेड क्रम में रखे जाते हैं। इसके परिणामस्वरूप, प्रत्येक रूट के पश्चिमी रूट से जुड़ने के लिए एक तीसरा बच्चा (जिसे डाइजक्स्ट्रा "स्टेपसन" कहते हैं) जोड़ा जाता है। इससे सभी वृक्षों को साथ मिलाकर एक समूचे वैश्विक हीप में मिलाया जाता है, जिसमें वैश्विक अधिकतम अंतिम में स्थित होता है।
यद्यपि, प्रत्येक नोड के स्टेपसन का स्थान स्थिर होता है, परंतु यह संपर्क केवल वृक्ष की जड़ों के लिए होता है, इसका अर्थ है कि जब वृक्षों को मिलाया जाता है, तब संपर्क हटा दिया जाता है। यह साधारित बच्चों से पृथक है, जो तब तक संपर्क में होते हैं जब तक माता-पिता उपस्थित होता हैं।
सॉर्टिंग की पहली (हीप बढ़ाने वाली) चरण में, एक बढ़ते हुए विस्तार के साथ एक प्रारंभिक हिस्सा को पुनर्व्यवस्थित किया जाता है क्योंकी प्रत्येक स्ट्रेच के लिए उसके उपवृक्ष हीप हो: किसी भी गैर-पत्ता स्थिति में, किसी भी गैर-पत्ता स्थिति पर विद्यमान प्रवेश न्यूनतम से न्यूनतम उसके बच्चों की स्थितियों के प्रवेश से न्यूनतम होता है। इसके अतिरिक्त, सभी रूट्स उनके स्टेपसन्स से न्यूनतम से न्यूनतम होते हैं।
दूसरे चरण में, अधिकतम नोड को सरणी के अंत से पृथक कर दिया जाता है, और ढेर अपरिवर्तनीय को उसके बच्चों के मध्य पुनः से स्थापित किया जाता है।
व्यावहारिक कार्यान्वयन में प्रायः लियोनार्डो संख्याओं L(k) की गणना की जरूरत होती है। डाइजक्स्ट्रा ने चतुर कोड प्रदान किया है जिसमें एक स्थायी संख्या चरोंवाले पूर्णांकीय मानों का उपयोग करके आवश्यक मानों की प्रभावी गणना की जाती है। वैकल्पिक रूप से, यदि सॉर्ट करने के लिए एरे का आकार N का एक सीमित बाउंड होता है, तो O(log N) अंतरिक्ष में पूर्व-गणित लियोनार्डो संख्या की एक पूर्वनिर्धारित सारणी संग्रहीत की जा सकती है।
संचालन
जब श्रेणी-ऑफ-हीप संरचना के विकास की दृष्टि से तकनीकी क्रिया के दो चरण एक-दूसरे के विपरीत होते हैं, तब वे एक मूल साधन का उपयोग करके कार्यान्वित किए जाते हैं, जो एक बाइनरी मैक्स-हीप में "सिफ्ट डाउन" आपरेशन के समकक्ष है।
छानना
मूल सिफ्ट-डाउन आपरेशन उस समय हीप अवियोग संरचना को पुनः स्थापित करता है जब इसका संभवतः केवल मूल तत्व नोड पर उल्लंघन किया जाता है। यदि मूल तत्व नोड अपने किसी भी बच्चे से न्यूनतम है, तो इसे उसके सबसे बड़े बच्चे के साथ परिवर्तित करता दिया जाता है और प्रक्रिया को उसके नए उपवृक्ष में मूल तत्व नोड के साथ दोहराया जाता है।
स्मूथसॉर्ट और एक बाइनरी मैक्स-हीप के मध्य अंतर यह है कि प्रत्येक स्ट्रेच की रूट को तीसरे "स्टेपसन" के संबंध में क्रमबद्ध किया जाना चाहिए: पिछले स्ट्रेच की रूट। इसलिए, सिफ्ट-डाउन प्रक्रिया चार-तरफी तुलनाएं के साथ प्रारंभ होती है जब तक स्टेपसन अधिकतम तत्व नहीं होता है, और पुनः तीन-तरफी तुलनाएं के साथ जब तक रूट नोड अपना अंतिम गृह नहीं मिलता है और नियम स्थापित किए जाते हैं।
प्रत्येक वृक्ष पूर्ण बाइनरी वृक्ष है: प्रत्येक नोड के दो बच्चे होते हैं या कोई नहीं होते। साधारित निहित बाइनरी हीप में जो एक बच्चा होता है, उसे संबोधित करने की कोई आवश्यकता नहीं होती है।
क्योंकि यहाँ O(log n) असंख्य स्ट्रेचेस हैं, जिनमें प्रत्येक एक वृक्ष O(log n) की गहराई का होता है, इसलिए प्रत्येक सिफ्ट-डाउन आपरेशन को करने का समय O(log n) से बंधा हुआ है।
दाईं ओर एक तत्व को सम्मलित करके ढेर क्षेत्र को बढ़ाना
जब एक अतिरिक्त तत्व को स्ट्रेच के अनुक्रम में सम्मलित करने पर विचार किया जाता है, तो यह या तो एक नया एक-तत्व स्ट्रेच बनाता है, या यह दोनों जड़ों के माता-पिता बनकर दो सबसे दाहिने स्ट्रेच को जोड़ता है और एक नया स्ट्रेच बनाता है। जो क्रम में दोनों को प्रतिस्थापित करता है। दोनों में से क्या होता है यह केवल वर्तमान में उपस्थित हिस्सों के आकार पर निर्भर करता है ,डाइक्स्ट्रा ने निर्धारित किया कि स्ट्रेच केवल तभी जोड़े जाएंगे जब उनके आकार L(k+1) और L(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 से न्यूनतम आकार के लिए पर्याप्त होगा। L(64) = 34335360355129 ≈ 245से न्यूनतम आकार के लिए एक 64-बिट वेक्टर कारगर होगा। सामान्यतः, प्रति आकार के 1/log2(φ) ≈ 1.44 बिट वेक्टर प्रति बिट की जगह चाहिए।
चिनार प्रकार
पॉपलर सॉर्ट, स्मूथसॉर्ट से प्रेरित एक सरल एल्गोरिदम है।[5] डच पोल्डर में देखे जाने वाले न्यूनतम होने वाले आकार के पेड़ की पंक्तियों के नाम पर रखा गया है। यह स्मूथसॉर्ट की तुलना में न्यूनतम तुलनाएं करता है जब इनपुट अधिकांश रूप से सॉर्ट नहीं होता है, परंतु सॉर्ट किए गए इनपुट के लिए रैखिक समय प्राप्त नहीं कर सकते हैं।
पॉपलर सॉर्ट में महत्वपूर्ण परिवर्तन है कि विभिन्न पेड़ों की जड़ों को क्रमबद्ध क्रम में नहीं रखा जाता है; उन्हें एक हीप में बांधने वाले "स्टेपसन" लिंक नहीं होते हैं। इसके अतिरिक्त, जब भी दूसरे चरण में हीप को छोटा किया जाता है, रूट्स को खोजने के लिए अधिकतम प्रविष्टि ढूंढी जाती है।.
पॉपलर सॉर्ट का सर्वोत्तम मामला रनटाइम O(n log n) होता है, क्योंकि इसमें n छोटने के चरण होते हैं, जिनमें से प्रत्येक में अधिकतम के लिए O(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.
बाहरी संबंध
- Commenपदted tranपदscriptionपदof EWD796a, 16-Aug-1981
- Detailed modernपदexplanपदationपदof Smoothsort
- wikibooks:Algorithm Implemenपदtationपद/Sortinपदg/Smoothsort
- Descriptionपदanपदd example implemenपदtationपद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.
