परिचय
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n log n) |
| Average performance | O(n log n) |
इंट्रोसॉर्ट या इंट्रोस्पेक्टिव सॉर्ट हाइब्रिड एल्गोरिदम छँटाई एल्गोरिथ्म है जो तेज़ औसत प्रदर्शन और (असममित रूप से) इष्टतम सबसे खराब स्थिति प्रदर्शन दोनों प्रदान करता है। यह जल्दी से सुलझाएं से शुरू होता है, जब रिकर्सन गहराई सॉर्ट किए जा रहे तत्वों की संख्या (लघुगणक) के आधार पर स्तर से अधिक हो जाती है तो यह हेप्सॉर्ट पर स्विच हो जाता है और जब तत्वों की संख्या कुछ सीमा से नीचे होती है तो यह सम्मिलन सॉर्ट पर स्विच हो जाता है। यह तीन एल्गोरिदम के अच्छे हिस्सों को जोड़ता है, जिसमें सामान्य डेटा सेट पर क्विकॉर्ट के बराबर व्यावहारिक प्रदर्शन और हीप सॉर्ट के कारण सबसे खराब स्थिति बिग-ओ संकेतन (एन लॉग एन) रनटाइम होता है। चूँकि यह जिन तीन एल्गोरिदम का उपयोग करता है वे तुलना प्रकार हैं, यह भी तुलना प्रकार है।
इंट्रोसॉर्ट का आविष्कार डेविड मूसर ने किया था Musser (1997), जिसमें उन्होंने आत्मचयन भी पेश किया, तुरंत चयन (क्विकसॉर्ट का प्रकार) पर आधारित हाइब्रिड चयन एल्गोरिदम, जो मध्यस्थों के मध्य में वापस आता है और इस प्रकार सबसे खराब स्थिति वाली रैखिक जटिलता प्रदान करता है, जो इष्टतम है। दोनों एल्गोरिदम को C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करने के उद्देश्य से पेश किया गया था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों थे, जिससे प्रदर्शन आवश्यकताओं को कड़ा किया जा सका।[1] इंट्रोसॉर्ट इन-प्लेस_एल्गोरिदम है न कि सॉर्टिंग_एल्गोरिदम#स्थिरता।[2]
छद्मकोड
यदि क्विकॉर्ट लेख में चर्चा किए गए प्रकार के हीपसॉर्ट कार्यान्वयन और विभाजन कार्य उपलब्ध हैं, तो इंट्रोसॉर्ट को संक्षेप में वर्णित किया जा सकता है
प्रक्रिया सॉर्ट (ए: सरणी): अधिकतम गहराई ← ⌊लॉग2(लंबाई(ए))⌋ × 2 परिचय (ए, अधिकतम गहराई) प्रक्रिया परिचय (ए, अधिकतम गहराई): n ← लंबाई(ए) यदि एन <16: प्रविष्टिसॉर्ट(ए) अन्यथा यदि अधिकतम गहराई = 0: हीपसॉर्ट(ए) अन्य: पी ← विभाजन (ए) // मान लें कि यह फ़ंक्शन धुरी चयन करता है, पी धुरी की अंतिम स्थिति है इंट्रोसॉर्ट(ए[1:पी-1], अधिकतम गहराई - 1) इंट्रोसॉर्ट(ए[पी+1:एन], अधिकतम गहराई - 1)
अधिकतम गहराई में कारक 2 मनमाना है; इसे व्यावहारिक प्रदर्शन के लिए ट्यून किया जा सकता है। A[i:j] वस्तुओं की सरणी टुकड़ा करना को दर्शाता है i को jदोनों सहित A[i] और A[j]. सूचकांकों को 1 (पहला तत्व) से शुरू माना जाता है A सरणी है A[1]).
विश्लेषण
क्विकसॉर्ट में, महत्वपूर्ण कार्यों में से धुरी का चयन करना है: वह तत्व जिसके चारों ओर सूची विभाजित है। सबसे सरल धुरी चयन एल्गोरिदम सूची के पहले या अंतिम तत्व को धुरी के रूप में लेना है, जिससे क्रमबद्ध या लगभग क्रमबद्ध इनपुट के मामले में खराब व्यवहार होता है। निकोलस विर्थ का संस्करण इन घटनाओं को रोकने के लिए मध्य तत्व का उपयोग करता है, जो O(n) में परिवर्तित हो जाता है2) काल्पनिक अनुक्रमों के लिए। माध्यिका-3 धुरी चयन एल्गोरिथ्म सूची के पहले, मध्य और अंतिम तत्वों का माध्यिका लेता है; हालाँकि, भले ही यह कई वास्तविक दुनिया के इनपुट पर अच्छा प्रदर्शन करता है, फिर भी औसत-3 किलर सूची तैयार करना संभव है जो इस धुरी चयन तकनीक के आधार पर क्विकॉर्ट की नाटकीय मंदी का कारण बनेगा।
मसर ने बताया कि 100,000 तत्वों के मध्य-में-3 किलर अनुक्रम पर, इंट्रोसॉर्ट का चलने का समय 3-मध्यम क्विकॉर्ट के 1/200 था। मसर ने रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक) की विलंबित छोटी सॉर्टिंग के सीपीयू कैश पर प्रभाव पर भी विचार किया, जहां प्रविष्टि सॉर्ट के ही पास में अंत में छोटी श्रेणियों को सॉर्ट किया जाता है। उन्होंने बताया कि यह कैश छूटने की संख्या को दोगुना कर सकता है, लेकिन डबल-एंडेड कतारों के साथ इसका प्रदर्शन काफी बेहतर था और इसे टेम्पलेट लाइब्रेरीज़ के लिए बनाए रखा जाना चाहिए, क्योंकि अन्य मामलों में तुरंत सॉर्ट करने से लाभ बहुत अच्छा नहीं था।
कार्यान्वयन
इंट्रोसॉर्ट या कुछ वेरिएंट का उपयोग कई मानक लाइब्रेरी सॉर्ट फ़ंक्शंस में किया जाता है, जिसमें कुछ सॉर्ट (सी ++) | सी ++ सॉर्ट कार्यान्वयन शामिल हैं।
जून 2000 सिलिकॉन ग्राफ़िक्स C++ मानक टेम्पलेट लाइब्रेरी stl_algo.h अस्थिर सॉर्ट का कार्यान्वयन हीपसॉर्ट पर स्विच करने के लिए रिकर्सन गहराई के साथ मसर इंट्रोसॉर्ट दृष्टिकोण का उपयोग करता है। पैरामीटर, 3 धुरी का मध्य चयन और 16 से छोटे विभाजन के लिए नथ अंतिम सम्मिलन सॉर्ट पास।
GNU मानक C++ लाइब्रेरी समान है: 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का उपयोग करता है2 n, इसके बाद 16 से छोटे विभाजनों पर सम्मिलन सॉर्ट किया जाता है।[3]
LLVM#C++_Standard_Library|LLVM libc++ 2×लॉग की अधिकतम गहराई के साथ इंट्रोसॉर्ट का भी उपयोग करता है2 n, हालाँकि विभिन्न डेटा प्रकारों के लिए प्रविष्टि सॉर्ट की आकार सीमा भिन्न होती है (यदि स्वैप तुच्छ हैं तो 30, अन्यथा 6)। साथ ही, 5 तक के आकार वाले ऐरे को अलग से संभाला जाता है।[4] कुटेनिन (2022) एलएलवीएम द्वारा किए गए कुछ परिवर्तनों का सिंहावलोकन प्रदान करता है, जिसमें द्विघातता के लिए 2022 फिक्स पर ध्यान केंद्रित किया गया है।[5]
Microsoft .NET फ्रेमवर्क बेस क्लास लाइब्रेरी, संस्करण 4.5 (2012) से शुरू होकर, सरल क्विकॉर्ट के बजाय इंट्रोसॉर्ट का उपयोग करती है।[6]
गो (प्रोग्रामिंग भाषा) इंट्रोसॉर्ट के संशोधन का उपयोग करता है: 12 या उससे कम तत्वों के स्लाइस के लिए यह इंसर्शन सॉर्ट का उपयोग करता है, और बड़े स्लाइस के लिए यह #pdqsort|पैटर्न-पराजित क्विकॉर्ट और धुरी चयन के लिए तीन मध्यस्थों के अधिक उन्नत मध्य का उपयोग करता है।[7] संस्करण 1.19 से पहले यह छोटे स्लाइस के लिए शेल सॉर्ट का उपयोग करता था।
जावा (प्रोग्रामिंग भाषा), संस्करण 14 (2020) से शुरू होकर, हाइब्रिड सॉर्टिंग एल्गोरिदम का उपयोग करता है जो अत्यधिक संरचित सरणियों के लिए मर्ज सॉर्ट का उपयोग करता है (ऐरे जो कम संख्या में क्रमबद्ध उपसरणी से बने होते हैं) और इंट्रोसॉर्ट अन्यथा इंट्स, लॉन्ग के सरणियों को सॉर्ट करने के लिए उपयोग करता है , तैरता है और दोगुना हो जाता है।[8]
वेरिएंट
पीडीक्यूसॉर्ट
पैटर्न-डिफ़ेटिंग क्विकसॉर्ट (पीडीक्यूसॉर्ट) निम्नलिखित सुधारों को शामिल करते हुए इंट्रोसॉर्ट का प्रकार है:[9]
- माध्यिका-तीन धुरी,
- शाखा गलत पूर्वानुमान दंड को कम करने के लिए ब्लॉकक्विकसॉर्ट विभाजन तकनीक,
- कुछ इनपुट पैटर्न (अनुकूली प्रकार) के लिए रैखिक समय प्रदर्शन,
- धीमे हीपसॉर्ट को आज़माने से पहले ख़राब मामलों पर एलिमेंट शफ़लिंग का उपयोग करें।
pdqsort का उपयोग रस्ट (प्रोग्रामिंग भाषा), GAP (कंप्यूटर बीजगणित प्रणाली) द्वारा किया जाता है।[10] और C++ लाइब्रेरी बूस्ट (C++ लाइब्रेरीज़)।[11]
संदर्भ
- ↑ "Generic Algorithms", David Musser
- ↑ "Know Your Sorting Algorithm | Set 2 (Introsort- C++'s Sorting Weapon)". 26 June 2016.
- ↑ libstdc++ Documentation: Sorting Algorithms
- ↑ libc++ source code: sort
- ↑ Kutenin, Danila (20 April 2022). "Changing std::sort at Google's Scale and Beyond". Experimental chill (in English).
- ↑ Array.Sort Method (Array)
- ↑ Go 1.20.3 source code
- ↑ Java 14 source code
- ↑ Peters, Orson R. L. (2021). "orlp/pdqsort: Pattern-defeating quicksort". GitHub (in English). arXiv:2106.05123.
- ↑ "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.
- ↑ Lammich, Peter (2020). इंट्रोसॉर्ट और पीडीक्यूसॉर्ट का कुशल सत्यापित कार्यान्वयन. IJCAR 2020: Automated Reasoning. Vol. 12167. pp. 307–323. doi:10.1007/978-3-030-51054-1_18.
सामान्य
- Musser, David R. (1997). "आत्मनिरीक्षण छँटाई और चयन एल्गोरिदम". Software: Practice and Experience. 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
- निकलॉस विर्थ. एल्गोरिदम और डेटा संरचनाएं। प्रेंटिस-हॉल, इंक., 1985। ISBN 0-13-022005-1.
श्रेणी:तुलना प्रकार
श्रेणी: उदाहरण छद्मकोड वाले लेख
