स्मूथसॉर्ट
 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][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. एक 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.
बाहरी संबंध
- 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.
