लाइब्रेरी सॉर्ट: Difference between revisions
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
'''<ब्लॉककोट>''' | '''<ब्लॉककोट>''' | ||
मान लीजिए कि एक लाइब्रेरियन को अपनी पुस्तकों को वर्णानुक्रम में एक लंबी शेल्फ पर संग्रहीत करना था, जो बाएं छोर पर ए से प्रारंभ | मान लीजिए कि एक लाइब्रेरियन को अपनी पुस्तकों को वर्णानुक्रम में एक लंबी शेल्फ पर संग्रहीत करना था, जो बाएं छोर पर ए से प्रारंभ होता था, और शेल्फ के साथ दाईं ओर जारी रहता था और जेड के अंत तक पुस्तकों के बीच कोई स्थान नहीं होता था। यदि लाइब्रेरियन ने एक नई किताब खरीदी है जो बी सेक्शन से संबंधित है, तो एक बार जब उन्हें बी सेक्शन में सही जगह मिल जाएगी, तो उन्हें बी के मध्य से लेकर ज़ेड तक हर किताब को स्थानांतरित करना होगा। नई किताब के लिए जगह बनाओ. यह एक प्रविष्टि प्रकार है. चूँकि , यदि उन्हें प्रत्येक अक्षर के बाद एक जगह छोड़नी होती है जब तक कि बी के बाद भी जगह होती है उन्हें नए के लिए जगह बनाने के लिए केवल कुछ किताबें हटानी पड़तीं। यह लाइब्रेरी सॉर्ट का मूल सिद्धांत है। | ||
एल्गोरिदम को 2004 में माइकल ए. बेंडर, मार्टिन फ़राच-कोल्टन और [[मिगुएल मठ|मिगुएल मोस्टेइरो]] द्वारा प्रस्तावित किया गया था।<ref>{{cite arXiv |eprint=cs/0407003 |title=सम्मिलन सॉर्ट O(n log n) है|date=1 July 2004 |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martín |authorlink2=Martin Farach-Colton |last3=Mosteiro |first3=Miguel A.}}</ref> और 2006 में प्रकाशित हुआ था।<ref name="definition">{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391–397 | date=June 2006 | last1=Bender | first1=Michael A. | last2=Farach-Colton | first2=Martín | authorlink2=Martin Farach-Colton | last3=Mosteiro | first3=Miguel A. | title=सम्मिलन सॉर्ट O(n log n) है| doi=10.1007/s00224-005-1237-z | url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | arxiv=cs/0407003 | s2cid=14701669 | access-date=2017-09-07 | archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | archive-date=2017-09-08 | url-status=dead }}</ref> | एल्गोरिदम को 2004 में माइकल ए. बेंडर, मार्टिन फ़राच-कोल्टन और [[मिगुएल मठ|मिगुएल मोस्टेइरो]] द्वारा प्रस्तावित किया गया था।<ref>{{cite arXiv |eprint=cs/0407003 |title=सम्मिलन सॉर्ट O(n log n) है|date=1 July 2004 |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martín |authorlink2=Martin Farach-Colton |last3=Mosteiro |first3=Miguel A.}}</ref> और 2006 में प्रकाशित हुआ था।<ref name="definition">{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391–397 | date=June 2006 | last1=Bender | first1=Michael A. | last2=Farach-Colton | first2=Martín | authorlink2=Martin Farach-Colton | last3=Mosteiro | first3=Miguel A. | title=सम्मिलन सॉर्ट O(n log n) है| doi=10.1007/s00224-005-1237-z | url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | arxiv=cs/0407003 | s2cid=14701669 | access-date=2017-09-07 | archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | archive-date=2017-09-08 | url-status=dead }}</ref> | ||
जिस सम्मिलन सॉर्ट पर यह आधारित है, लाइब्रेरी सॉर्ट एक तुलनात्मक सॉर्ट है; चूँकि इसे सम्मिलन सॉर्ट के O(n<sup>2</sup>) के अतिरिक्त | जिस सम्मिलन सॉर्ट पर यह आधारित है, लाइब्रेरी सॉर्ट एक तुलनात्मक सॉर्ट है; चूँकि इसे सम्मिलन सॉर्ट के O(n<sup>2</sup>) के अतिरिक्त O(n log n) समय ([[जल्दी से सुलझाएं|क्विकसॉर्ट]] की तुलना में) में चलने की उच्च संभावना दिखाई गई थी। पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के स्पष्ट एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी। | ||
मूलभूत प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,<ref name="definition" /> किंतु ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अतिरिक्त , यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की आश्वासन देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान अवयव के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक अवयव के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है। | मूलभूत प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,<ref name="definition" /> किंतु ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अतिरिक्त , यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की आश्वासन देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान अवयव के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक अवयव के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है। | ||
एक और दोष यह है कि इसे [[ऑनलाइन एल्गोरिदम]] के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से परिवर्तन करना संभव नहीं है। यदि इस परिवर्तन | एक और दोष यह है कि इसे [[ऑनलाइन एल्गोरिदम]] के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से परिवर्तन करना संभव नहीं है। यदि इस परिवर्तन के बिना उपयोग किया जाए, तो यह आसानी से द्विघात व्यवहार में परिवर्तित हो सकता है। | ||
इंसर्शन सॉर्ट की एक अशक्ति यह है कि इसके लिए बड़ी संख्या में स्वैप ऑपरेशन की आवश्यकता हो सकती है और यदि मेमोरी राइट मूल्यवान है तो यह मूल्यवान हो सकता है। प्रविष्टि चरण में लाइब्रेरी प्रकार में कुछ सीमा तक सुधार हो सकता है, क्योंकि जगह बनाने के लिए कम अवयव को स्थानांतरित करने की आवश्यकता होती है, किंतु पुनर्संतुलन चरण में अतिरिक्त लागत भी जुड़ जाती है। इसके अतिरिक्त संदर्भ की स्थानीयता [[मर्ज़ सॉर्ट]] की तुलना में व्यर्थ होगी, क्योंकि यादृच्छिक डेटा सेट से प्रत्येक प्रविष्टि उस मेमोरी तक पहुंच सकती है जो अब कैश में नहीं है, विशेष रूप से बड़े डेटा सेट के साथ है। | इंसर्शन सॉर्ट की एक अशक्ति यह है कि इसके लिए बड़ी संख्या में स्वैप ऑपरेशन की आवश्यकता हो सकती है और यदि मेमोरी राइट मूल्यवान है तो यह मूल्यवान हो सकता है। प्रविष्टि चरण में लाइब्रेरी प्रकार में कुछ सीमा तक सुधार हो सकता है, क्योंकि जगह बनाने के लिए कम अवयव को स्थानांतरित करने की आवश्यकता होती है, किंतु पुनर्संतुलन चरण में अतिरिक्त लागत भी जुड़ जाती है। इसके अतिरिक्त संदर्भ की स्थानीयता [[मर्ज़ सॉर्ट]] की तुलना में व्यर्थ होगी, क्योंकि यादृच्छिक डेटा सेट से प्रत्येक प्रविष्टि उस मेमोरी तक पहुंच सकती है जो अब कैश में नहीं है, विशेष रूप से बड़े डेटा सेट के साथ है। | ||
| Line 30: | Line 30: | ||
===एल्गोरिदम === | ===एल्गोरिदम === | ||
मान लीजिए कि हमारे पास n अवयव की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग n | मान लीजिए कि हमारे पास n अवयव की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग n राउंड में काम करता है। प्रत्येक राउंड में हम उतने ही अवयव सम्मिलित करते हैं जितने अंतिम एरे में हैं, एरे को पुनः संतुलित करने से पहले डालने की स्थिति का पता लगाने के लिए, हम अंतिम सरणी में बाइनरी सर्च लागू करते हैं और तब तक निम्नलिखित अवयव को स्वैप करते हैं जब तक कि हम रिक्त स्थान पर नहीं पहुंच जाते। एक बार राउंड ख़त्म होने के बाद, हम प्रत्येक अवयव के बीच रिक्त स्थान डालकर अंतिम सरणी को फिर से संतुलित करते हैं। | ||
एल्गोरिथम के तीन महत्वपूर्ण चरण निम्नलिखित हैं: | एल्गोरिथम के तीन महत्वपूर्ण चरण निम्नलिखित हैं: | ||
| Line 36: | Line 36: | ||
# बाइनरी सर्च: पहले से डाले गए अवयव के अंदर बाइनरी सर्च प्रयुक्त करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य अवयव में रिक्त स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है। | # बाइनरी सर्च: पहले से डाले गए अवयव के अंदर बाइनरी सर्च प्रयुक्त करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य अवयव में रिक्त स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है। | ||
# सम्मिलन: अवयव को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित अवयव को 1 स्थिति से तब तक स्वैप करना जब तक कोई रिक्त स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है। | # सम्मिलन: अवयव को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित अवयव को 1 स्थिति से तब तक स्वैप करना जब तक कोई रिक्त स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है। | ||
# पुनः संतुलन: सरणी में अवयव की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की निवेश पहले से डाले गए अवयव की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल निवेश | # पुनः संतुलन: सरणी में अवयव की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की निवेश पहले से डाले गए अवयव की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल निवेश रैखिक होती है। | ||
===छद्मकोड=== | ===छद्मकोड=== | ||
'''procedure''' rebalance(A, begin, end) '''is''' | '''procedure''' rebalance(A, begin, end) '''is''' | ||
r ← end | |||
w ← end × 2 | |||
'''while''' r ≥ begin '''do''' | |||
A[w] ← A[r] | |||
A[w-1] ← gap | |||
r ← r − 1 | |||
w ← w − 2 | |||
'''procedure''' sort(A) '''is''' | '''procedure''' sort(A) '''is''' | ||
n ← length(A) | |||
S ← new array of n gaps | |||
'''for''' i ← 1 to floor(log2(n-1)) '''do''' | |||
rebalance(S, 1, 2^(i-1))) | |||
'''for''' j ← 2^(i-1) to 2^i '''do''' | |||
ins ← binarysearch(A[j], S, 2^i) | |||
insert A[j] at S[ins] | |||
यहां, <code>binarysearch(el, A, k)</code> | यहां, <code>binarysearch(el, A, k)</code> {{mvar|A}} के पहले {{mvar|k}} तत्वों में बाइनरी खोज करता है, अंतराल को छोड़कर, तत्व {{mvar|el}} का पता लगाने के लिए एक जगह खोजने के लिए सम्मिलन को भरे हुए तत्वों पर अंतराल का पक्ष लेना चाहिए। | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 12:56, 22 July 2023
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | |
| Best-case performance | |
| Average performance | |
| Worst-case space complexity |
लाइब्रेरी सॉर्ट, या गैप्ड इंसर्शन सॉर्ट एक सॉर्टिंग एल्गोरिदम है जो इंसर्शन सॉर्ट का उपयोग करता है, किंतु बाद के इंसर्शन में तेजी लाने के लिए सरणी में अंतराल के साथ नाम एक सादृश्य से आता है:
<ब्लॉककोट>
मान लीजिए कि एक लाइब्रेरियन को अपनी पुस्तकों को वर्णानुक्रम में एक लंबी शेल्फ पर संग्रहीत करना था, जो बाएं छोर पर ए से प्रारंभ होता था, और शेल्फ के साथ दाईं ओर जारी रहता था और जेड के अंत तक पुस्तकों के बीच कोई स्थान नहीं होता था। यदि लाइब्रेरियन ने एक नई किताब खरीदी है जो बी सेक्शन से संबंधित है, तो एक बार जब उन्हें बी सेक्शन में सही जगह मिल जाएगी, तो उन्हें बी के मध्य से लेकर ज़ेड तक हर किताब को स्थानांतरित करना होगा। नई किताब के लिए जगह बनाओ. यह एक प्रविष्टि प्रकार है. चूँकि , यदि उन्हें प्रत्येक अक्षर के बाद एक जगह छोड़नी होती है जब तक कि बी के बाद भी जगह होती है उन्हें नए के लिए जगह बनाने के लिए केवल कुछ किताबें हटानी पड़तीं। यह लाइब्रेरी सॉर्ट का मूल सिद्धांत है।
एल्गोरिदम को 2004 में माइकल ए. बेंडर, मार्टिन फ़राच-कोल्टन और मिगुएल मोस्टेइरो द्वारा प्रस्तावित किया गया था।[1] और 2006 में प्रकाशित हुआ था।[2]
जिस सम्मिलन सॉर्ट पर यह आधारित है, लाइब्रेरी सॉर्ट एक तुलनात्मक सॉर्ट है; चूँकि इसे सम्मिलन सॉर्ट के O(n2) के अतिरिक्त O(n log n) समय (क्विकसॉर्ट की तुलना में) में चलने की उच्च संभावना दिखाई गई थी। पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के स्पष्ट एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी।
मूलभूत प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,[2] किंतु ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अतिरिक्त , यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की आश्वासन देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान अवयव के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक अवयव के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है।
एक और दोष यह है कि इसे ऑनलाइन एल्गोरिदम के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से परिवर्तन करना संभव नहीं है। यदि इस परिवर्तन के बिना उपयोग किया जाए, तो यह आसानी से द्विघात व्यवहार में परिवर्तित हो सकता है।
इंसर्शन सॉर्ट की एक अशक्ति यह है कि इसके लिए बड़ी संख्या में स्वैप ऑपरेशन की आवश्यकता हो सकती है और यदि मेमोरी राइट मूल्यवान है तो यह मूल्यवान हो सकता है। प्रविष्टि चरण में लाइब्रेरी प्रकार में कुछ सीमा तक सुधार हो सकता है, क्योंकि जगह बनाने के लिए कम अवयव को स्थानांतरित करने की आवश्यकता होती है, किंतु पुनर्संतुलन चरण में अतिरिक्त लागत भी जुड़ जाती है। इसके अतिरिक्त संदर्भ की स्थानीयता मर्ज़ सॉर्ट की तुलना में व्यर्थ होगी, क्योंकि यादृच्छिक डेटा सेट से प्रत्येक प्रविष्टि उस मेमोरी तक पहुंच सकती है जो अब कैश में नहीं है, विशेष रूप से बड़े डेटा सेट के साथ है।
कार्यान्वयन
एल्गोरिदम
मान लीजिए कि हमारे पास n अवयव की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग n राउंड में काम करता है। प्रत्येक राउंड में हम उतने ही अवयव सम्मिलित करते हैं जितने अंतिम एरे में हैं, एरे को पुनः संतुलित करने से पहले डालने की स्थिति का पता लगाने के लिए, हम अंतिम सरणी में बाइनरी सर्च लागू करते हैं और तब तक निम्नलिखित अवयव को स्वैप करते हैं जब तक कि हम रिक्त स्थान पर नहीं पहुंच जाते। एक बार राउंड ख़त्म होने के बाद, हम प्रत्येक अवयव के बीच रिक्त स्थान डालकर अंतिम सरणी को फिर से संतुलित करते हैं।
एल्गोरिथम के तीन महत्वपूर्ण चरण निम्नलिखित हैं:
- बाइनरी सर्च: पहले से डाले गए अवयव के अंदर बाइनरी सर्च प्रयुक्त करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य अवयव में रिक्त स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है।
- सम्मिलन: अवयव को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित अवयव को 1 स्थिति से तब तक स्वैप करना जब तक कोई रिक्त स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है।
- पुनः संतुलन: सरणी में अवयव की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की निवेश पहले से डाले गए अवयव की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल निवेश रैखिक होती है।
छद्मकोड
procedure rebalance(A, begin, end) is
r ← end
w ← end × 2
while r ≥ begin do
A[w] ← A[r]
A[w-1] ← gap
r ← r − 1
w ← w − 2
procedure sort(A) is
n ← length(A)
S ← new array of n gaps
for i ← 1 to floor(log2(n-1)) do
rebalance(S, 1, 2^(i-1)))
for j ← 2^(i-1) to 2^i do
ins ← binarysearch(A[j], S, 2^i)
insert A[j] at S[ins]
यहां, binarysearch(el, A, k) A के पहले k तत्वों में बाइनरी खोज करता है, अंतराल को छोड़कर, तत्व el का पता लगाने के लिए एक जगह खोजने के लिए सम्मिलन को भरे हुए तत्वों पर अंतराल का पक्ष लेना चाहिए।
संदर्भ
- ↑ Bender, Michael A.; Farach-Colton, Martín; Mosteiro, Miguel A. (1 July 2004). "सम्मिलन सॉर्ट O(n log n) है". arXiv:cs/0407003.
- ↑ 2.0 2.1 Bender, Michael A.; Farach-Colton, Martín; Mosteiro, Miguel A. (June 2006). "सम्मिलन सॉर्ट O(n log n) है" (PDF). Theory of Computing Systems. 39 (3): 391–397. arXiv:cs/0407003. doi:10.1007/s00224-005-1237-z. S2CID 14701669. Archived from the original (PDF) on 2017-09-08. Retrieved 2017-09-07.
