परिचय
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n log n) |
| Average performance | O(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]
संदर्भ
- ↑ "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.
श्रेणी:तुलना प्रकार
श्रेणी: उदाहरण स्यूडोकोड वाले लेख
