परिचय - Revision history

Manidh at 11:03, 7 July 2023

2023-07-07T11:03:39Z

@@ Line 79: / Line 79: @@
 श्रेणी: उदाहरण स्यूडोकोड वाले लेख
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 27/06/2023]]
-[[Category:Vigyan Ready]]
+[[Category:Lua-based templates]]

Indicwiki: 5 revisions imported from :alpha:परिचय

2023-07-05T09:42:31Z

5 revisions imported from alpha:परिचय

← Older revision	Revision as of 15:12, 5 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-05T07:16:41Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 12:46, 5 July 2023
Line 81:		Line 81:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]
			[[Category:Vigyan Ready]]

alpha>AmitKumar at 13:00, 3 July 2023

2023-07-03T13:00:03Z

← Older revision		Revision as of 18:30, 3 July 2023
Line 11:		Line 11:
	}}		}}

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

	अतः इंट्रोसॉर्ट का आविष्कार [[ डेविड मूसर \|डेविड मूसर]] ने किया था {{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 \| 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 \| Set 2 (Introsort- C++'s Sorting Weapon)\|date = 26 June 2016}}</ref>
	==स्यूडोकोड ==		==स्यूडोकोड ==
	यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध किये जाते हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है<syntaxhighlight>		यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध किये जाते हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है<syntaxhighlight>
Line 31:		Line 31:
	introsort(A[p+1:n], maxdepth - 1)		introsort(A[p+1:n], maxdepth - 1)
	</syntaxhighlight>		</syntaxhighlight>
	~~प्रक्रिया सॉर्ट (ए: सरणी):~~
	~~अधिकतम गहराई ← ⌊लॉग<sub>2</sub>(लंबाई(ए))⌋ × 2~~
	~~परिचय (ए, अधिकतम गहराई)~~

	~~प्रक्रिया परिचय (ए, अधिकतम गहराई):~~
	~~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++ सॉर्ट कार्यान्वयन भी सम्मिलित किये जाते हैं।		इस प्रकार से इंट्रोसॉर्ट या कुछ वैरिएंट का उपयोग कई मानक लाइब्रेरी सॉर्ट फ़ंक्शंस में किया जाता है, जिसमें कुछ 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 से छोटे विभाजन के लिए नथ अंतिम सम्मिलन सॉर्ट पास का उपयोग करता है।
Line 90:		Line 77:
	श्रेणी:तुलना प्रकार		श्रेणी:तुलना प्रकार

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

	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]

alpha>AmitKumar at 12:55, 3 July 2023

2023-07-03T12:55:05Z

Show changes

alpha>AmitKumar at 11:23, 3 July 2023

2023-07-03T11:23:12Z

Show changes

alpha>Indicwiki: Created page with "{{Short description|Hybrid sorting algorithm}} {{Infobox Algorithm |class=Sorting algorithm |image= |caption= |data=Array |time=O(''n'' log ''n'')..."

2023-06-27T11:28:44Z

Created page with "{{Short description|Hybrid sorting algorithm}} {{Infobox Algorithm |class=Sorting algorithm |image= |caption= |data=Array |time=O(''n'' log ''n'')..."

New page

{{Short description|Hybrid sorting algorithm}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|caption=
|data=[[Array data structure|Array]]
|time=O(''n'' log ''n'')
|average-time=O(''n'' log ''n'')
|space=
|optimal=yes
}}

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

इंट्रोसॉर्ट का आविष्कार [[ डेविड मूसर ]] ने किया था {{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 | Set 2 (Introsort- C++'s Sorting Weapon)|date = 26 June 2016}}</ref>

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

प्रक्रिया सॉर्ट (ए: सरणी):
अधिकतम गहराई ← ⌊लॉग2(लंबाई(ए))⌋ × 2
परिचय (ए, अधिकतम गहराई)

प्रक्रिया परिचय (ए, अधिकतम गहराई):
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]}}).

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

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

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

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

GNU मानक C++ लाइब्रेरी समान है: 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का उपयोग करता है2 n, इसके बाद 16 से छोटे विभाजनों पर एक सम्मिलन सॉर्ट किया जाता है।<ref>[https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html libstdc++ Documentation: Sorting Algorithms]</ref>
LLVM#C++_Standard_Library|LLVM libc++ 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का भी उपयोग करता है2 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>

== वेरिएंट ==

=== पीडीक्यूसॉर्ट ===
पैटर्न-डिफ़ेटिंग क्विकसॉर्ट (पीडीक्यूसॉर्ट) निम्नलिखित सुधारों को शामिल करते हुए इंट्रोसॉर्ट का एक प्रकार है:<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>

==संदर्भ==
{{reflist}}

===सामान्य===
{{refbegin}}
* {{Cite journal | last = Musser | first = David R. | author-link = David Musser | title = आत्मनिरीक्षण छँटाई और चयन एल्गोरिदम| url = http://www.cs.rpi.edu/~musser/gp/introsort.ps| doi = 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# | journal = Software: Practice and Experience | volume = 27 | issue = 8 | pages = 983–993 | year = 1997 }}
* निकलॉस विर्थ. एल्गोरिदम और डेटा संरचनाएं। प्रेंटिस-हॉल, इंक., 1985। {{ISBN|0-13-022005-1}}.
{{refend}}

{{sorting}}

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

[[Category: Machine Translated Page]]
[[Category:Created On 27/06/2023]]