लाइब्रेरी सॉर्ट: Difference between revisions

लाइब्रेरी सॉर्ट
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity

Revision as of 12:53, 22 July 2023

लाइब्रेरी सॉर्ट, या गैप्ड इंसर्शन सॉर्ट एक सॉर्टिंग एल्गोरिदम है जो इंसर्शन सॉर्ट का उपयोग करता है, किंतु बाद के इंसर्शन में तेजी लाने के लिए सरणी में अंतराल के साथ नाम एक सादृश्य से आता है:

<ब्लॉककोट>

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

एल्गोरिदम को 2004 में माइकल ए. बेंडर, मार्टिन फ़राच-कोल्टन और मिगुएल मोस्टेइरो द्वारा प्रस्तावित किया गया था।^[1] और 2006 में प्रकाशित हुआ था।^[2]

जिस सम्मिलन सॉर्ट पर यह आधारित है, लाइब्रेरी सॉर्ट एक तुलनात्मक सॉर्ट है; चूँकि इसे सम्मिलन सॉर्ट के O(n²) के अतिरिक्त 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.

बाहरी संबंध

Gapped Insertion Sort

[1] Bender, Michael A.; Farach-Colton, Martín; Mosteiro, Miguel A. (1 July 2004). "सम्मिलन सॉर्ट O(n log n) है". arXiv:cs/0407003.

[definition-2] 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.

[1]

[2]

@@ Line 9: / Line 9: @@
 |optimal=?
 }}
-लाइब्रेरी सॉर्ट, या गैप्ड [[ सम्मिलन सॉर्ट |सम्मिलन सॉर्ट]] एक [[छँटाई एल्गोरिथ्म]] है जो इंसर्शन सॉर्ट का उपयोग करता है, लेकिन बाद के इंसर्शन में तेजी लाने के लिए सरणी में अंतराल के साथ। नाम एक सादृश्य से आता है:
-<ब्लॉककोट>मान लीजिए कि एक लाइब्रेरियन को अपनी पुस्तकों को वर्णानुक्रम में एक लंबी शेल्फ पर संग्रहीत करना था, जो बाएं छोर पर ए से शुरू होता था, और शेल्फ के साथ दाईं ओर जारी रहता था और जेड के अंत तक पुस्तकों के बीच कोई स्थान नहीं होता था। यदि लाइब्रेरियन ने एक नई किताब खरीदी है जो बी सेक्शन से संबंधित है, तो एक बार जब उन्हें बी सेक्शन में सही जगह मिल जाएगी, तो उन्हें बी के मध्य से लेकर ज़ेड तक हर किताब को स्थानांतरित करना होगा। नई किताब के लिए जगह बनाओ. यह एक प्रविष्टि प्रकार है. हालाँकि, यदि उन्हें प्रत्येक अक्षर के बाद एक जगह छोड़नी होती, जब तक कि बी के बाद भी जगह होती, उन्हें नए के लिए जगह बनाने के लिए केवल कुछ किताबें हटानी पड़तीं। यह लाइब्रेरी सॉर्ट का मूल सिद्धांत है।</blockquote>
-एल्गोरिदम को 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) के बजाय O(n लॉग n) समय ([[जल्दी से सुलझाएं]] की तुलना में) में चलने की उच्च संभावना दिखाई गई थी।<sup>2</sup>). पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के सटीक एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी।
-बुनियादी प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,<ref name="definition" />लेकिन ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अलावा, यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की गारंटी देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान तत्वों के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक तत्व के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है।
+लाइब्रेरी सॉर्ट, या गैप्ड इंसर्शन सॉर्ट एक सॉर्टिंग एल्गोरिदम है जो इंसर्शन सॉर्ट का उपयोग करता है, किंतु बाद के इंसर्शन में तेजी लाने के लिए सरणी में अंतराल के साथ नाम एक सादृश्य से आता है:
-एक और दोष यह है कि इसे [[ऑनलाइन एल्गोरिदम]] के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से फेरबदल करना संभव नहीं है। यदि इस फेरबदल के बिना उपयोग किया जाए, तो यह आसानी से द्विघात व्यवहार में परिवर्तित हो सकता है।
+'''<ब्लॉककोट>'''
-इंसर्शन सॉर्ट की एक कमजोरी यह है कि इसके लिए बड़ी संख्या में स्वैप ऑपरेशन की आवश्यकता हो सकती है और यदि मेमोरी राइट महंगा है तो यह महंगा हो सकता है। प्रविष्टि चरण में लाइब्रेरी प्रकार में कुछ हद तक सुधार हो सकता है, क्योंकि जगह बनाने के लिए कम तत्वों को स्थानांतरित करने की आवश्यकता होती है, लेकिन पुनर्संतुलन चरण में अतिरिक्त लागत भी जुड़ जाती है। इसके अलावा, संदर्भ की स्थानीयता [[मर्ज़ सॉर्ट]] की तुलना में खराब होगी, क्योंकि यादृच्छिक डेटा सेट से प्रत्येक प्रविष्टि उस मेमोरी तक पहुंच सकती है जो अब कैश में नहीं है, खासकर बड़े डेटा सेट के साथ।
+मान लीजिए कि एक लाइब्रेरियन को अपनी पुस्तकों को वर्णानुक्रम में एक लंबी शेल्फ पर संग्रहीत करना था, जो बाएं छोर पर ए से प्रारंभ  होता था, और शेल्फ के साथ दाईं ओर जारी रहता था और जेड के अंत तक पुस्तकों के बीच कोई स्थान नहीं होता था। यदि लाइब्रेरियन ने एक नई किताब खरीदी है जो बी सेक्शन से संबंधित है, तो एक बार जब उन्हें बी सेक्शन में सही जगह मिल जाएगी, तो उन्हें बी के मध्य से लेकर ज़ेड तक हर किताब को स्थानांतरित करना होगा। नई किताब के लिए जगह बनाओ. यह एक प्रविष्टि प्रकार है. चूँकि , यदि उन्हें प्रत्येक अक्षर के बाद एक जगह छोड़नी होती है  जब तक कि बी के बाद भी जगह होती है उन्हें नए के लिए जगह बनाने के लिए केवल कुछ किताबें हटानी पड़तीं। यह लाइब्रेरी सॉर्ट का मूल सिद्धांत है।
+एल्गोरिदम को 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 log n) समय ([[जल्दी से सुलझाएं|क्विकसॉर्ट]]  की तुलना में) में चलने की उच्च संभावना दिखाई गई थी। पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के स्पष्ट  एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी।
+मूलभूत प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,<ref name="definition" /> किंतु ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अतिरिक्त , यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की आश्वासन देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान अवयव के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक अवयव के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है।
+एक और दोष यह है कि इसे [[ऑनलाइन एल्गोरिदम]] के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से परिवर्तन करना संभव नहीं है। यदि इस परिवर्तन  के बिना उपयोग किया जाए, तो यह आसानी से द्विघात व्यवहार में परिवर्तित हो सकता है।
+इंसर्शन सॉर्ट की एक अशक्ति यह है कि इसके लिए बड़ी संख्या में स्वैप ऑपरेशन की आवश्यकता हो सकती है और यदि मेमोरी राइट मूल्यवान है तो यह मूल्यवान हो सकता है। प्रविष्टि चरण में लाइब्रेरी प्रकार में कुछ सीमा तक सुधार हो सकता है, क्योंकि जगह बनाने के लिए कम अवयव को स्थानांतरित करने की आवश्यकता होती है, किंतु पुनर्संतुलन चरण में अतिरिक्त लागत भी जुड़ जाती है। इसके अतिरिक्त संदर्भ की स्थानीयता [[मर्ज़ सॉर्ट]] की तुलना में व्यर्थ होगी, क्योंकि यादृच्छिक डेटा सेट से प्रत्येक प्रविष्टि उस मेमोरी तक पहुंच सकती है जो अब कैश में नहीं है, विशेष रूप से बड़े डेटा सेट के साथ है।
 ==कार्यान्वयन==
 ===एल्गोरिदम ===
-मान लीजिए कि हमारे पास n तत्वों की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग एन राउंड में काम करता है। प्रत्येक राउंड में हम उतने ही तत्व सम्मिलित करते हैं जितने अंतिम एरे में हैं, एरे को पुनः संतुलित करने से पहले। डालने की स्थिति का पता लगाने के लिए, हम अंतिम सरणी में बाइनरी सर्च लागू करते हैं और तब तक निम्नलिखित तत्वों को स्वैप करते हैं जब तक कि हम खाली स्थान पर नहीं पहुंच जाते। एक बार राउंड ख़त्म होने के बाद, हम प्रत्येक तत्व के बीच रिक्त स्थान डालकर अंतिम सरणी को फिर से संतुलित करते हैं।
+मान लीजिए कि हमारे पास n अवयव की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग n  राउंड में काम करता है। प्रत्येक राउंड में हम उतने ही अवयव सम्मिलित करते हैं जितने अंतिम एरे में हैं, एरे को पुनः संतुलित करने से पहले डालने की स्थिति का पता लगाने के लिए, हम अंतिम सरणी में बाइनरी सर्च लागू करते हैं और तब तक निम्नलिखित अवयव को स्वैप करते हैं जब तक कि हम रिक्त स्थान पर नहीं पहुंच जाते। एक बार राउंड ख़त्म होने के बाद, हम प्रत्येक अवयव के बीच रिक्त स्थान डालकर अंतिम सरणी को फिर से संतुलित करते हैं।
 एल्गोरिथम के तीन महत्वपूर्ण चरण निम्नलिखित हैं:
-# बाइनरी सर्च: पहले से डाले गए तत्वों के भीतर बाइनरी सर्च लागू करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य तत्व में खाली स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है।
+# बाइनरी सर्च: पहले से डाले गए अवयव के अंदर बाइनरी सर्च प्रयुक्त करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य अवयव में रिक्त स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है।
-# सम्मिलन: तत्व को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित तत्वों को 1 स्थिति से तब तक स्वैप करना जब तक कोई खाली स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है।
+# सम्मिलन: अवयव को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित अवयव को 1 स्थिति से तब तक स्वैप करना जब तक कोई रिक्त स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है।
-# पुनः संतुलन: सरणी में तत्वों की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की लागत पहले से डाले गए तत्वों की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल लागत भी रैखिक होती है।
+# पुनः संतुलन: सरणी में अवयव की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की निवेश पहले से डाले गए अवयव की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल निवेश  रैखिक होती है।
 ===छद्मकोड===
-  प्रक्रिया पुनर्संतुलन (ए, प्रारंभ, अंत) है
+  '''procedure''' rebalance(A, begin, end) '''is'''
-  आर ← अंत
+     r ← end
-  w ← अंत × 2
+     w ← end × 2
-  जबकि r ≥ आरंभ करें
+     '''while''' r ≥ begin '''do'''
-  ए[डब्ल्यू] ← ए[आर]
+         A[w] ← A[r]
-  ए[डब्ल्यू-1] ← गैप
+         A[w-1] ← gap
-  आर ← आर − 1
+         r ← r − 1
-  डब्ल्यू ← डब्ल्यू − 2
+         w ← w − 2
-  प्रक्रिया सॉर्ट (ए) है
+  '''procedure''' sort(A) '''is'''
-  n ← लंबाई(ए)
+     n ← length(A)
-  एस ← एन अंतराल की नई सरणी
+     S ← new array of n gaps
-  i ← 1 से मंजिल तक (log2(n-1)) करें
+     '''for''' i ← 1 to floor(log2(n-1)) '''do'''
-  पुनर्संतुलन(एस, 1, 2^(आई-1)))
+         rebalance(S, 1, 2^(i-1)))
-  j ← 2^(i-1) से 2^i के लिए
+         '''for''' j ← 2^(i-1) to 2^i '''do'''
-  इन्स ← बाइनरी सर्च(ए[जे], एस, 2^आई)
+             ins ← binarysearch(A[j], S, 2^i)
-  S[ins] पर A[j] डालें
+             insert A[j] at S[ins]
-यहाँ, <code>binarysearch(el, A, k)</code> पहले में बाइनरी खोज करता है {{mvar|k}} घटक {{mvar|A}}, रिक्त स्थान को पार करते हुए, एक ऐसा स्थान ढूंढें जहां तत्व का पता लगाया जा सके {{mvar|el}}. सम्मिलन को भरे हुए तत्वों पर अंतराल का पक्ष लेना चाहिए।
+यहां, <code>binarysearch(el, A, k)</code>  {{mvar|A}} के पहले {{mvar|k}} तत्वों में बाइनरी खोज करता है, अंतराल को छोड़कर, तत्व {{mvar|el}} का पता लगाने के लिए एक जगह खोजने के लिए सम्मिलन को भरे हुए तत्वों पर अंतराल का पक्ष लेना चाहिए।
 == संदर्भ ==

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

लाइब्रेरी सॉर्ट: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:53, 22 July 2023

Contents

कार्यान्वयन

एल्गोरिदम

छद्मकोड

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

लाइब्रेरी सॉर्ट: Difference between revisions

Revision as of 12:53, 22 July 2023

कार्यान्वयन

एल्गोरिदम

छद्मकोड

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories