परिचय: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Hybrid sorting algorithm}} {{Infobox Algorithm |class=Sorting algorithm |image= |caption= |data=Array |time=O(''n'' log ''n'')...")
 
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 11: Line 11:
}}
}}


इंट्रोसॉर्ट या इंट्रोस्पेक्टिव सॉर्ट एक [[हाइब्रिड एल्गोरिदम]] [[छँटाई एल्गोरिथ्म]] है जो तेज़ औसत प्रदर्शन और (असममित रूप से) इष्टतम सबसे खराब स्थिति प्रदर्शन दोनों प्रदान करता है। यह [[जल्दी से सुलझाएं]] से शुरू होता है, जब रिकर्सन गहराई सॉर्ट किए जा रहे तत्वों की संख्या (लघुगणक) के आधार पर एक स्तर से अधिक हो जाती है तो यह हेप्सॉर्ट पर स्विच हो जाता है और जब तत्वों की संख्या कुछ सीमा से नीचे होती है तो यह [[ सम्मिलन सॉर्ट ]] पर स्विच हो जाता है। यह तीन एल्गोरिदम के अच्छे हिस्सों को जोड़ता है, जिसमें सामान्य डेटा सेट पर क्विकॉर्ट के बराबर व्यावहारिक प्रदर्शन और हीप सॉर्ट के कारण सबसे खराब स्थिति [[ बिग-ओ संकेतन ]] (''एन'' लॉग ''एन'') रनटाइम होता है। चूँकि यह जिन तीन एल्गोरिदम का उपयोग करता है वे तुलना प्रकार हैं, यह भी एक तुलना प्रकार है।
'''इंट्रोसॉर्ट''' या '''इंट्रोस्पेक्टिव सॉर्ट''' [[हाइब्रिड एल्गोरिदम]] [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिदम]] होते है जो तीव्र औसत प्रदर्शन और (असममित रूप से) इष्टतम अधिक व्यर्थ स्थिति प्रदर्शन दोनों प्रदान करता है। यह [[जल्दी से सुलझाएं|क्विकसॉर्ट]] से प्रारंभ होता है, जब रिकर्सन गहराई सॉर्ट किए जा रहे तत्वों की संख्या (लघुगणक) के आधार पर स्तर से अधिक हो जाती है तो यह हेप्सॉर्ट पर स्विच हो जाता है और जब तत्वों की संख्या कुछ सीमा से नीचे होती है तो यह [[ सम्मिलन सॉर्ट |सम्मिलन सॉर्ट]] पर स्विच हो जाता है। यह तीन एल्गोरिदम के अच्छे भागो को जोड़ता है, जिसमें सामान्य डेटा सेट पर क्विकॉर्ट के समान व्यावहारिक प्रदर्शन और हीप सॉर्ट के कारण अधिक व्यर्थ स्थिति [[ बिग-ओ संकेतन |ओ]] (''एन'' लॉग ''एन'') रनटाइम होता है। चूँकि यह जिन तीन एल्गोरिदम का उपयोग करता है इस प्रकार की तुलना का उपयोग किया जाता हैं।


इंट्रोसॉर्ट का आविष्कार [[ डेविड मूसर ]] ने किया था {{harvtxt|Musser|1997}}, जिसमें उन्होंने [[ आत्मचयन ]] भी पेश किया, [[ तुरंत चयन ]] (क्विकसॉर्ट का एक प्रकार) पर आधारित एक हाइब्रिड चयन एल्गोरिदम, जो मध्यस्थों के मध्य में वापस आता है और इस प्रकार सबसे खराब स्थिति वाली रैखिक जटिलता प्रदान करता है, जो इष्टतम है। दोनों एल्गोरिदम को C++ मानक लाइब्रेरी के लिए [[सामान्य एल्गोरिदम]] प्रदान करने के उद्देश्य से पेश किया गया था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों थे, जिससे प्रदर्शन आवश्यकताओं को कड़ा किया जा सका।<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref> इंट्रोसॉर्ट इन-प्लेस_एल्गोरिदम है न कि सॉर्टिंग_एल्गोरिदम#स्थिरता।<ref>{{Cite web|url=https://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/|title = Know Your Sorting Algorithm &#124; Set 2 (Introsort- C++'s Sorting Weapon)|date = 26 June 2016}}</ref>
अतः इंट्रोसॉर्ट का आविष्कार [[ डेविड मूसर |डेविड मूसर]] ने किया था {{harvtxt|मूसर|1997}}, जिसमें उन्होंने [[ आत्मचयन |आत्मचयन]] भी प्रस्तुत किया गया , [[ तुरंत चयन |चयन एल्गोरिदम]] (क्विकसॉर्ट का प्रकार) पर आधारित हाइब्रिड चयन एल्गोरिदम, जोकी मध्यस्थों के मध्य में वापस आते है और इस प्रकार अधिक व्यर्थ स्थिति वाली रैखिक जटिलता प्रदान करता है, जो इष्टतम होते है। इस प्रकार से दोनों एल्गोरिदम को C++ स्टैंडर्ड लाइब्रेरी के लिए [[सामान्य एल्गोरिदम]] प्रदान करने के उद्देश्य से प्रस्तुत किया गया था, जिसमें तीव्र औसत प्रदर्शन और इष्टतम अधिक व्यर्थ प्रदर्शन दोनों थे, जिससे प्रदर्शन आवश्यकताओं को श्रेष्ट किया जा सकता था ।<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref> इस प्रकार से इंट्रोसॉर्ट अपनी जगह पर है और स्थिर नहीं है।<ref>{{Cite web|url=https://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/|title = Know Your Sorting Algorithm &#124; Set 2 (Introsort- C++'s Sorting Weapon)|date = 26 June 2016}}</ref>
==स्यूडोकोड ==
यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध किये जाते हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है<syntaxhighlight>
procedure sort(A : array):
    maxdepth ← ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)


 
procedure introsort(A, maxdepth):
==छद्मकोड==
    n ← length(A)
यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है
    if n < 16:
 
        insertionsort(A)
प्रक्रिया सॉर्ट (ए: सरणी):
    else if maxdepth = 0:
    अधिकतम गहराई ← ⌊लॉग<sub>2</sub>(लंबाई(ए))⌋ × 2
        heapsort(A)
    परिचय (ए, अधिकतम गहराई)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)
</syntaxhighlight>
   
   
प्रक्रिया परिचय (ए, अधिकतम गहराई):
    n ← लंबाई(ए)
    यदि एन <16:
        प्रविष्टिसॉर्ट(ए)
    अन्यथा यदि अधिकतम गहराई = 0:
        हीपसॉर्ट(ए)
    अन्य:
        पी ← विभाजन (ए) ''// मान लें कि यह फ़ंक्शन धुरी चयन करता है, पी धुरी की अंतिम स्थिति है''
        इंट्रोसॉर्ट(ए[1:पी-1], अधिकतम गहराई - 1)
        इंट्रोसॉर्ट(ए[पी+1:एन], अधिकतम गहराई - 1)


अधिकतम गहराई में कारक 2 मनमाना है; इसे व्यावहारिक प्रदर्शन के लिए ट्यून किया जा सकता है। {{math|''A''[''i'':''j'']}} वस्तुओं की [[सरणी टुकड़ा करना]] को दर्शाता है {{mvar|i}} को {{mvar|j}}दोनों सहित {{math|''A''[''i'']}} और {{math|''A''[''j'']}}. सूचकांकों को 1 (पहला तत्व) से शुरू माना जाता है {{mono|A}} सरणी है {{mono|A[1]}}).
अधिकतम गहराई में कारक 2 मनमाना है; इसे व्यावहारिक प्रदर्शन के लिए ट्यून किया जा सकता है। {{math|''A''[''i'':''j'']}} वस्तुओं की [[सरणी टुकड़ा करना|सरणी टुश्रेष्ट करना]] को दर्शाता है {{mvar|i}} को {{mvar|j}}दोनों सहित {{math|''A''[''i'']}} और {{math|''A''[''j'']}}. सूचकांकों को 1 (पहला तत्व) से प्रारंभ माना जाता है {{mono|A}} सरणी है {{mono|A[1]}}).


==विश्लेषण==
==विश्लेषण==
क्विकसॉर्ट में, महत्वपूर्ण कार्यों में से एक धुरी का चयन करना है: वह तत्व जिसके चारों ओर सूची विभाजित है। सबसे सरल धुरी चयन एल्गोरिदम सूची के पहले या अंतिम तत्व को धुरी के रूप में लेना है, जिससे क्रमबद्ध या लगभग क्रमबद्ध इनपुट के मामले में खराब व्यवहार होता है। [[ निकोलस विर्थ ]] का संस्करण इन घटनाओं को रोकने के लिए मध्य तत्व का उपयोग करता है, जो O(n) में परिवर्तित हो जाता है<sup>2</sup>) काल्पनिक अनुक्रमों के लिए। माध्यिका-3 धुरी चयन एल्गोरिथ्म सूची के पहले, मध्य और अंतिम तत्वों का माध्यिका लेता है; हालाँकि, भले ही यह कई वास्तविक दुनिया के इनपुट पर अच्छा प्रदर्शन करता है, फिर भी एक औसत-3 किलर सूची तैयार करना संभव है जो इस धुरी चयन तकनीक के आधार पर क्विकॉर्ट की नाटकीय मंदी का कारण बनेगा।
इस प्रकार से क्विकसॉर्ट में, महत्वपूर्ण कार्यों में से धुरी का चयन किया जाता है: वह तत्व जिसके चारों ओर सूची विभाजित कोती है। सबसे सरल धुरी चयन एल्गोरिदम सूची के प्रथम या अंतिम तत्व को धुरी के रूप में माना जाता है, जिससे क्रमबद्ध या लगभग क्रमबद्ध इनपुट के विषय में निकृष्ट व्यवहार होता है। [[ निकोलस विर्थ |निकोलस विर्थ]] का संस्करण इन घटनाओं को रोकने के लिए मध्य तत्व का उपयोग करता है, जो काल्पनिक अनुक्रमों के लिए O(''n''<sup>2</sup>) में परिवर्तित हो जाता है।) इस प्रकार से काल्पनिक अनुक्रमों के लिए। माध्यिका-3 धुरी चयन एल्गोरिथ्म सूची के पहले, मध्य और अंतिम तत्वों का माध्यिका लेता है; चूंकि , भले ही यह कई वास्तविक दुनिया के इनपुट पर अच्छा प्रदर्शन करता है, फिर भी औसत-3 किलर सूची तैयार करना संभव है जो इस धुरी चयन विधि के आधार पर क्विकॉर्ट की नाटकीय मंदी का कारण बनेगा।


मसर ने बताया कि 100,000 तत्वों के मध्य-में-3 किलर अनुक्रम पर, इंट्रोसॉर्ट का चलने का समय 3-मध्यम क्विकॉर्ट के 1/200 था। मसर ने [[रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक)]] की विलंबित छोटी सॉर्टिंग के [[सीपीयू कैश]] पर प्रभाव पर भी विचार किया, जहां प्रविष्टि सॉर्ट के एक ही पास में अंत में छोटी श्रेणियों को सॉर्ट किया जाता है। उन्होंने बताया कि यह कैश छूटने की संख्या को दोगुना कर सकता है, लेकिन डबल-एंडेड कतारों के साथ इसका प्रदर्शन काफी बेहतर था और इसे टेम्पलेट लाइब्रेरीज़ के लिए बनाए रखा जाना चाहिए, क्योंकि अन्य मामलों में तुरंत सॉर्ट करने से लाभ बहुत अच्छा नहीं था।
अतः मसर द्बवारा बताया गया कि 100,000 तत्वों के मध्य-में-3 किलर अनुक्रम पर, इंट्रोसॉर्ट का चलने का समय 3-मध्यम क्विकॉर्ट के 1/200 था। मसर ने [[रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक)]] की विलंबित छोटी सॉर्टिंग के [[सीपीयू कैश]] पर प्रभाव पर भी विचार किया, जहां प्रविष्टि सॉर्ट के ही पास में अंत में छोटी श्रेणियों को सॉर्ट किया जाता है। उन्होंने बताया कि यह कैश छूटने की संख्या को दोगुना कर सकता है, किंतु डबल-एंडेड कतारों के साथ इसका प्रदर्शन अधिक श्रेष्ट माना जाता था और इसे टेम्पलेट लाइब्रेरीज़ के लिए बनाए रखा जाना चाहिए, क्योंकि अन्य विषय में तुरंत सॉर्ट करने से लाभ बहुत अच्छा नहीं था।


==कार्यान्वयन==
==कार्यान्वयन==
इंट्रोसॉर्ट या कुछ वेरिएंट का उपयोग कई मानक लाइब्रेरी सॉर्ट फ़ंक्शंस में किया जाता है, जिसमें कुछ सॉर्ट (सी ++) | सी ++ सॉर्ट कार्यान्वयन शामिल हैं।
इस प्रकार से इंट्रोसॉर्ट या कुछ वैरिएंट का उपयोग कई मानक लाइब्रेरी सॉर्ट फ़ंक्शंस में किया जाता है, जिसमें कुछ C++ सॉर्ट कार्यान्वयन भी सम्मिलित किये जाते हैं।
 
और जून 2000 [[सिलिकॉन ग्राफ़िक्स]] C++ [[मानक टेम्पलेट लाइब्रेरी]] [http://www.sgi.com/tech/stl/stl_algo.h stl_algo.h] अस्थिर सॉर्ट का कार्यान्वयन हीपसॉर्ट पर स्विच करने के लिए रिकर्सन गहराई के साथ मसर इंट्रोसॉर्ट दृष्टिकोण का उपयोग करता है। पैरामीटर, मध्य-ऑफ-3 पिवट चयन और 16 से छोटे विभाजन के लिए नथ अंतिम सम्मिलन सॉर्ट पास का उपयोग करता है।


जून 2000 [[सिलिकॉन ग्राफ़िक्स]] C++ [[मानक टेम्पलेट लाइब्रेरी]] [http://www.sgi.com/tech/stl/stl_algo.h stl_algo.h] अस्थिर सॉर्ट का कार्यान्वयन हीपसॉर्ट पर स्विच करने के लिए रिकर्सन गहराई के साथ मसर इंट्रोसॉर्ट दृष्टिकोण का उपयोग करता है। एक पैरामीटर, 3 धुरी का मध्य चयन और 16 से छोटे विभाजन के लिए नथ अंतिम सम्मिलन सॉर्ट पास।
GNU मानक C++ लाइब्रेरी समान है: 2×log<sub>2</sub> ''n'', की अधिकतम गहराई के साथ इंट्रोसॉर्ट का उपयोग करता है, इसके बाद 16 से छोटे विभाजनों पर एक प्रविष्टि सॉर्ट करता है।<ref>[https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html libstdc++ Documentation: Sorting Algorithms]</ref>


GNU मानक C++ लाइब्रेरी समान है: 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का उपयोग करता है<sub>2</sub> n, इसके बाद 16 से छोटे विभाजनों पर एक सम्मिलन सॉर्ट किया जाता है।<ref>[https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html libstdc++ Documentation: Sorting Algorithms]</ref>
LLVM या libc++ 2×log<sub>2</sub> ''n'', की अधिकतम गहराई के साथ इंट्रोसॉर्ट का भी उपयोग करता है, हालांकि विभिन्न डेटा प्रकारों के लिए इंसर्शन सॉर्ट की आकार सीमा अलग-अलग होती है (यदि स्वैप तुच्छ हैं तो 30, अन्यथा 6)। साथ ही, 5 तक के आकार वाले ऐरे को अलग से संभाला जाता है।<ref>[https://github.com/llvm/llvm-project/blob/368faacac7525e538fa6680aea74e19a75e3458d/libcxx/include/__algorithm/sort.h#L272 libc++ source code: sort]</ref> कुटेनिन (2022) एलएलवीएम द्वारा किए गए कुछ परिवर्तनों का सिंहावलोकन प्रदान करता है, जिसमें द्विघातता के लिए 2022 फिक्स पर ध्यान केंद्रित किया गया है।<ref name="Kutenin-LLVM">{{cite web |last1=Kutenin |first1=Danila |title=Changing std::sort at Google’s Scale and Beyond |url=https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/comment-page-1 |website=Experimental chill |language=en |date=20 April 2022}}</ref>
LLVM#C++_Standard_Library|LLVM libc++ 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का भी उपयोग करता है<sub>2</sub> n, हालाँकि विभिन्न डेटा प्रकारों के लिए प्रविष्टि सॉर्ट की आकार सीमा भिन्न होती है (यदि स्वैप तुच्छ हैं तो 30, अन्यथा 6)। साथ ही, 5 तक के आकार वाले ऐरे को अलग से संभाला जाता है।<ref>[https://github.com/llvm/llvm-project/blob/368faacac7525e538fa6680aea74e19a75e3458d/libcxx/include/__algorithm/sort.h#L272 libc++ source code: sort]</ref> कुटेनिन (2022) एलएलवीएम द्वारा किए गए कुछ परिवर्तनों का एक सिंहावलोकन प्रदान करता है, जिसमें द्विघातता के लिए 2022 फिक्स पर ध्यान केंद्रित किया गया है।<ref name="Kutenin-LLVM">{{cite web |last1=Kutenin |first1=Danila |title=Changing std::sort at Google’s Scale and Beyond |url=https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/comment-page-1 |website=Experimental chill |language=en |date=20 April 2022}}</ref>
Microsoft .NET फ्रेमवर्क [[बेस क्लास लाइब्रेरी]], संस्करण 4.5 (2012) से शुरू होकर, सरल क्विकॉर्ट के बजाय इंट्रोसॉर्ट का उपयोग करती है।<ref>[http://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx Array.Sort Method (Array)]</ref>
गो (प्रोग्रामिंग भाषा) इंट्रोसॉर्ट के एक संशोधन का उपयोग करता है: 12 या उससे कम तत्वों के स्लाइस के लिए यह इंसर्शन सॉर्ट का उपयोग करता है, और बड़े स्लाइस के लिए यह #pdqsort|पैटर्न-पराजित क्विकॉर्ट और धुरी चयन के लिए तीन मध्यस्थों के अधिक उन्नत मध्य का उपयोग करता है।<ref>[https://github.com/golang/go/blob/go1.20.3/src/sort/zsortfunc.go#L61 Go 1.20.3 source code]</ref> संस्करण 1.19 से पहले यह छोटे स्लाइस के लिए शेल सॉर्ट का उपयोग करता था।


[[जावा (प्रोग्रामिंग भाषा)]], संस्करण 14 (2020) से शुरू होकर, एक हाइब्रिड सॉर्टिंग एल्गोरिदम का उपयोग करता है जो अत्यधिक संरचित सरणियों के लिए मर्ज सॉर्ट का उपयोग करता है (ऐरे जो कम संख्या में क्रमबद्ध उपसरणी से बने होते हैं) और इंट्रोसॉर्ट अन्यथा इंट्स, लॉन्ग के सरणियों को सॉर्ट करने के लिए उपयोग करता है , तैरता है और दोगुना हो जाता है।<ref>[https://github.com/openjdk/jdk/blob/jdk-14-ga/src/java.base/share/classes/java/util/DualPivotQuicksort.java#L178 Java 14 source code]</ref>
माइक्रोसॉफ्ट .नेट फ्रेमवर्क [[बेस क्लास लाइब्रेरी]], संस्करण 4.5 (2012) से प्रारंभ होकर, सरल क्विकॉर्ट के बजाय इंट्रोसॉर्ट का उपयोग करती है।<ref>[http://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx Array.Sort Method (Array)]</ref>


गो (प्रोग्रामिंग भाषा) इंट्रोसॉर्ट के संशोधन का उपयोग करता है: 12 या उससे कम तत्वों के स्लाइस के लिए यह इंसर्शन सॉर्ट का उपयोग करता है, और और बड़े स्लाइस के लिए यह पैटर्न-पराजित क्विकॉर्ट और धुरी चयन के लिए तीन मध्यस्थों के अधिक उन्नत मध्य का उपयोग करता है।<ref>[https://github.com/golang/go/blob/go1.20.3/src/sort/zsortfunc.go#L61 Go 1.20.3 source code]</ref> संस्करण 1.19 से प्रथम यह छोटे स्लाइस के लिए शेल सॉर्ट का उपयोग करता था।


[[जावा (प्रोग्रामिंग भाषा)]], संस्करण 14 (2020) से प्रारंभ होकर, हाइब्रिड सॉर्टिंग एल्गोरिदम का उपयोग करता है जो अत्यधिक संरचित सरणियों के लिए मर्ज सॉर्ट का उपयोग करता है (ऐरे जो कम संख्या में क्रमबद्ध उपसरणी से बने होते हैं) और इंट्रोसॉर्ट अन्यथा इंट्स, लॉन्ग के सरणियों को सॉर्ट करने के लिए उपयोग करता है , तैरता है और दोगुना हो जाता है।<ref>[https://github.com/openjdk/jdk/blob/jdk-14-ga/src/java.base/share/classes/java/util/DualPivotQuicksort.java#L178 Java 14 source code]</ref>
== वेरिएंट ==
== वेरिएंट ==


=== पीडीक्यूसॉर्ट ===
=== पीडीक्यूसॉर्ट ===
पैटर्न-डिफ़ेटिंग क्विकसॉर्ट (पीडीक्यूसॉर्ट) निम्नलिखित सुधारों को शामिल करते हुए इंट्रोसॉर्ट का एक प्रकार है:<ref>{{cite web |last1=Peters|first1=Orson R. L. |title=orlp/pdqsort: Pattern-defeating quicksort. |url=https://github.com/orlp/pdqsort |website=GitHub |year=2021 |language=en |arxiv=2106.05123}}</ref>
पैटर्न-डिफ़ेटिंग क्विकसॉर्ट (पीडीक्यूसॉर्ट) निम्नलिखित सुधारों को सम्मिलित करते हुए इंट्रोसॉर्ट का प्रकार है:<ref>{{cite web |last1=Peters|first1=Orson R. L. |title=orlp/pdqsort: Pattern-defeating quicksort. |url=https://github.com/orlp/pdqsort |website=GitHub |year=2021 |language=en |arxiv=2106.05123}}</ref>
* माध्यिका-तीन धुरी,
* माध्यिका-तीन धुरी,
* शाखा गलत पूर्वानुमान दंड को कम करने के लिए ब्लॉकक्विकसॉर्ट विभाजन तकनीक,
* शाखा गलत पूर्वानुमान दंड को कम करने के लिए ब्लॉकक्विकसॉर्ट विभाजन विधि ,
* कुछ इनपुट पैटर्न ([[अनुकूली प्रकार]]) के लिए रैखिक समय प्रदर्शन,
* कुछ इनपुट पैटर्न ([[अनुकूली प्रकार]]) के लिए रैखिक समय प्रदर्शन,
* धीमे हीपसॉर्ट को आज़माने से पहले ख़राब मामलों पर एलिमेंट शफ़लिंग का उपयोग करें।
* धीमे हीपसॉर्ट को परखने से प्रथम व्यथ विषय पर एलिमेंट शफ़लिंग का उपयोग करें।
 
pdqsort का उपयोग रस्ट (प्रोग्रामिंग भाषा), [[GAP (कंप्यूटर बीजगणित प्रणाली)]] द्वारा किया जाता है।<ref>{{cite web |title=slice.sort_unstable(&mut self) |url=https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable |website=Rust |quote=The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.}}</ref> और C++ लाइब्रेरी बूस्ट (C++ लाइब्रेरीज़)।<ref>{{cite conference |last1=Lammich |first1=Peter |title=इंट्रोसॉर्ट और पीडीक्यूसॉर्ट का कुशल सत्यापित कार्यान्वयन|doi-access=free |conference=IJCAR 2020: Automated Reasoning |date=2020 |volume=12167 |pages=307–323 |doi=10.1007/978-3-030-51054-1_18}}</ref>
 


पीडीक्यूसॉर्ट का उपयोग रस्ट (प्रोग्रामिंग भाषा), [[GAP (कंप्यूटर बीजगणित प्रणाली)]] द्वारा किया जाता है।<ref>{{cite web |title=slice.sort_unstable(&mut self) |url=https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable |website=Rust |quote=The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.}}</ref> और C++ लाइब्रेरी बूस्ट (C++ लाइब्रेरीज़)।<ref>{{cite conference |last1=Lammich |first1=Peter |title=इंट्रोसॉर्ट और पीडीक्यूसॉर्ट का कुशल सत्यापित कार्यान्वयन|doi-access=free |conference=IJCAR 2020: Automated Reasoning |date=2020 |volume=12167 |pages=307–323 |doi=10.1007/978-3-030-51054-1_18}}</ref>
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}


===सामान्य===
===सामान्य===
Line 81: Line 76:


श्रेणी:तुलना प्रकार
श्रेणी:तुलना प्रकार
श्रेणी: उदाहरण छद्मकोड वाले लेख


श्रेणी: उदाहरण स्यूडोकोड वाले लेख


[[Category: Machine Translated Page]]
[[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:Pages with syntax highlighting 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]]

Latest revision as of 16:33, 7 July 2023

परिचय
ClassSorting algorithm
Data structureArray
Worst-case performanceO(n log n)
Average performanceO(n log n)

इंट्रोसॉर्ट या इंट्रोस्पेक्टिव सॉर्ट हाइब्रिड एल्गोरिदम सॉर्टिंग एल्गोरिदम होते है जो तीव्र औसत प्रदर्शन और (असममित रूप से) इष्टतम अधिक व्यर्थ स्थिति प्रदर्शन दोनों प्रदान करता है। यह क्विकसॉर्ट से प्रारंभ होता है, जब रिकर्सन गहराई सॉर्ट किए जा रहे तत्वों की संख्या (लघुगणक) के आधार पर स्तर से अधिक हो जाती है तो यह हेप्सॉर्ट पर स्विच हो जाता है और जब तत्वों की संख्या कुछ सीमा से नीचे होती है तो यह सम्मिलन सॉर्ट पर स्विच हो जाता है। यह तीन एल्गोरिदम के अच्छे भागो को जोड़ता है, जिसमें सामान्य डेटा सेट पर क्विकॉर्ट के समान व्यावहारिक प्रदर्शन और हीप सॉर्ट के कारण अधिक व्यर्थ स्थिति ओ (एन लॉग एन) रनटाइम होता है। चूँकि यह जिन तीन एल्गोरिदम का उपयोग करता है इस प्रकार की तुलना का उपयोग किया जाता हैं।

अतः इंट्रोसॉर्ट का आविष्कार डेविड मूसर ने किया था मूसर (1997), जिसमें उन्होंने आत्मचयन भी प्रस्तुत किया गया , चयन एल्गोरिदम (क्विकसॉर्ट का प्रकार) पर आधारित हाइब्रिड चयन एल्गोरिदम, जोकी मध्यस्थों के मध्य में वापस आते है और इस प्रकार अधिक व्यर्थ स्थिति वाली रैखिक जटिलता प्रदान करता है, जो इष्टतम होते है। इस प्रकार से दोनों एल्गोरिदम को C++ स्टैंडर्ड लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करने के उद्देश्य से प्रस्तुत किया गया था, जिसमें तीव्र औसत प्रदर्शन और इष्टतम अधिक व्यर्थ प्रदर्शन दोनों थे, जिससे प्रदर्शन आवश्यकताओं को श्रेष्ट किया जा सकता था ।[1] इस प्रकार से इंट्रोसॉर्ट अपनी जगह पर है और स्थिर नहीं है।[2]

स्यूडोकोड

यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध किये जाते हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है

procedure sort(A : array):
    maxdepth ← ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 16:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)


अधिकतम गहराई में कारक 2 मनमाना है; इसे व्यावहारिक प्रदर्शन के लिए ट्यून किया जा सकता है। A[i:j] वस्तुओं की सरणी टुश्रेष्ट करना को दर्शाता है i को jदोनों सहित A[i] और A[j]. सूचकांकों को 1 (पहला तत्व) से प्रारंभ माना जाता है A सरणी है A[1]).

विश्लेषण

इस प्रकार से क्विकसॉर्ट में, महत्वपूर्ण कार्यों में से धुरी का चयन किया जाता है: वह तत्व जिसके चारों ओर सूची विभाजित कोती है। सबसे सरल धुरी चयन एल्गोरिदम सूची के प्रथम या अंतिम तत्व को धुरी के रूप में माना जाता है, जिससे क्रमबद्ध या लगभग क्रमबद्ध इनपुट के विषय में निकृष्ट व्यवहार होता है। निकोलस विर्थ का संस्करण इन घटनाओं को रोकने के लिए मध्य तत्व का उपयोग करता है, जो काल्पनिक अनुक्रमों के लिए O(n2) में परिवर्तित हो जाता है।) इस प्रकार से काल्पनिक अनुक्रमों के लिए। माध्यिका-3 धुरी चयन एल्गोरिथ्म सूची के पहले, मध्य और अंतिम तत्वों का माध्यिका लेता है; चूंकि , भले ही यह कई वास्तविक दुनिया के इनपुट पर अच्छा प्रदर्शन करता है, फिर भी औसत-3 किलर सूची तैयार करना संभव है जो इस धुरी चयन विधि के आधार पर क्विकॉर्ट की नाटकीय मंदी का कारण बनेगा।

अतः मसर द्बवारा बताया गया कि 100,000 तत्वों के मध्य-में-3 किलर अनुक्रम पर, इंट्रोसॉर्ट का चलने का समय 3-मध्यम क्विकॉर्ट के 1/200 था। मसर ने रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक) की विलंबित छोटी सॉर्टिंग के सीपीयू कैश पर प्रभाव पर भी विचार किया, जहां प्रविष्टि सॉर्ट के ही पास में अंत में छोटी श्रेणियों को सॉर्ट किया जाता है। उन्होंने बताया कि यह कैश छूटने की संख्या को दोगुना कर सकता है, किंतु डबल-एंडेड कतारों के साथ इसका प्रदर्शन अधिक श्रेष्ट माना जाता था और इसे टेम्पलेट लाइब्रेरीज़ के लिए बनाए रखा जाना चाहिए, क्योंकि अन्य विषय में तुरंत सॉर्ट करने से लाभ बहुत अच्छा नहीं था।

कार्यान्वयन

इस प्रकार से इंट्रोसॉर्ट या कुछ वैरिएंट का उपयोग कई मानक लाइब्रेरी सॉर्ट फ़ंक्शंस में किया जाता है, जिसमें कुछ C++ सॉर्ट कार्यान्वयन भी सम्मिलित किये जाते हैं।

और जून 2000 सिलिकॉन ग्राफ़िक्स C++ मानक टेम्पलेट लाइब्रेरी stl_algo.h अस्थिर सॉर्ट का कार्यान्वयन हीपसॉर्ट पर स्विच करने के लिए रिकर्सन गहराई के साथ मसर इंट्रोसॉर्ट दृष्टिकोण का उपयोग करता है। पैरामीटर, मध्य-ऑफ-3 पिवट चयन और 16 से छोटे विभाजन के लिए नथ अंतिम सम्मिलन सॉर्ट पास का उपयोग करता है।

GNU मानक C++ लाइब्रेरी समान है: 2×log2 n, की अधिकतम गहराई के साथ इंट्रोसॉर्ट का उपयोग करता है, इसके बाद 16 से छोटे विभाजनों पर एक प्रविष्टि सॉर्ट करता है।[3]

LLVM या libc++ 2×log2 n, की अधिकतम गहराई के साथ इंट्रोसॉर्ट का भी उपयोग करता है, हालांकि विभिन्न डेटा प्रकारों के लिए इंसर्शन सॉर्ट की आकार सीमा अलग-अलग होती है (यदि स्वैप तुच्छ हैं तो 30, अन्यथा 6)। साथ ही, 5 तक के आकार वाले ऐरे को अलग से संभाला जाता है।[4] कुटेनिन (2022) एलएलवीएम द्वारा किए गए कुछ परिवर्तनों का सिंहावलोकन प्रदान करता है, जिसमें द्विघातता के लिए 2022 फिक्स पर ध्यान केंद्रित किया गया है।[5]

माइक्रोसॉफ्ट .नेट फ्रेमवर्क बेस क्लास लाइब्रेरी, संस्करण 4.5 (2012) से प्रारंभ होकर, सरल क्विकॉर्ट के बजाय इंट्रोसॉर्ट का उपयोग करती है।[6]

गो (प्रोग्रामिंग भाषा) इंट्रोसॉर्ट के संशोधन का उपयोग करता है: 12 या उससे कम तत्वों के स्लाइस के लिए यह इंसर्शन सॉर्ट का उपयोग करता है, और और बड़े स्लाइस के लिए यह पैटर्न-पराजित क्विकॉर्ट और धुरी चयन के लिए तीन मध्यस्थों के अधिक उन्नत मध्य का उपयोग करता है।[7] संस्करण 1.19 से प्रथम यह छोटे स्लाइस के लिए शेल सॉर्ट का उपयोग करता था।

जावा (प्रोग्रामिंग भाषा), संस्करण 14 (2020) से प्रारंभ होकर, हाइब्रिड सॉर्टिंग एल्गोरिदम का उपयोग करता है जो अत्यधिक संरचित सरणियों के लिए मर्ज सॉर्ट का उपयोग करता है (ऐरे जो कम संख्या में क्रमबद्ध उपसरणी से बने होते हैं) और इंट्रोसॉर्ट अन्यथा इंट्स, लॉन्ग के सरणियों को सॉर्ट करने के लिए उपयोग करता है , तैरता है और दोगुना हो जाता है।[8]

वेरिएंट

पीडीक्यूसॉर्ट

पैटर्न-डिफ़ेटिंग क्विकसॉर्ट (पीडीक्यूसॉर्ट) निम्नलिखित सुधारों को सम्मिलित करते हुए इंट्रोसॉर्ट का प्रकार है:[9]

  • माध्यिका-तीन धुरी,
  • शाखा गलत पूर्वानुमान दंड को कम करने के लिए ब्लॉकक्विकसॉर्ट विभाजन विधि ,
  • कुछ इनपुट पैटर्न (अनुकूली प्रकार) के लिए रैखिक समय प्रदर्शन,
  • धीमे हीपसॉर्ट को परखने से प्रथम व्यथ विषय पर एलिमेंट शफ़लिंग का उपयोग करें।

पीडीक्यूसॉर्ट का उपयोग रस्ट (प्रोग्रामिंग भाषा), GAP (कंप्यूटर बीजगणित प्रणाली) द्वारा किया जाता है।[10] और C++ लाइब्रेरी बूस्ट (C++ लाइब्रेरीज़)।[11]

संदर्भ

  1. ↑ "Generic Algorithms", David Musser
  2. ↑ "Know Your Sorting Algorithm | Set 2 (Introsort- C++'s Sorting Weapon)". 26 June 2016.
  3. ↑ libstdc++ Documentation: Sorting Algorithms
  4. ↑ libc++ source code: sort
  5. ↑ Kutenin, Danila (20 April 2022). "Changing std::sort at Google's Scale and Beyond". Experimental chill (in English).
  6. ↑ Array.Sort Method (Array)
  7. ↑ Go 1.20.3 source code
  8. ↑ Java 14 source code
  9. ↑ Peters, Orson R. L. (2021). "orlp/pdqsort: Pattern-defeating quicksort". GitHub (in English). arXiv:2106.05123.
  10. ↑ "slice.sort_unstable(&mut self)". Rust. The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.
  11. ↑ Lammich, Peter (2020). इंट्रोसॉर्ट और पीडीक्यूसॉर्ट का कुशल सत्यापित कार्यान्वयन. IJCAR 2020: Automated Reasoning. Vol. 12167. pp. 307–323. doi:10.1007/978-3-030-51054-1_18.

सामान्य

श्रेणी:तुलना प्रकार

श्रेणी: उदाहरण स्यूडोकोड वाले लेख

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=परिचय&oldid=209617’