लाइब्रेरी सॉर्ट

लाइब्रेरी सॉर्ट

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$
Best-case performance	$O(n\log n)$
Average performance	$O(n\log n)$
Worst-case space complexity	$O(n)$

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

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

एल्गोरिदम को 2004 में माइकल ए. बेंडर, मार्टिन फ़राच-कोल्टन और मिगुएल मठ द्वारा प्रस्तावित किया गया था। और 2006 में प्रकाशित हुआ था। जिस सम्मिलन सॉर्ट पर यह आधारित है, लाइब्रेरी सॉर्ट एक तुलनात्मक सॉर्ट है; हालाँकि, इसे सम्मिलन सॉर्ट के O(n) के बजाय O(n लॉग n) समय (जल्दी से सुलझाएं की तुलना में) में चलने की उच्च संभावना दिखाई गई थी।²). पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के सटीक एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी।

बुनियादी प्रविष्टि प्रकार की तुलना में, लाइब्रेरी प्रकार का दोष यह है कि इसमें अंतराल के लिए अतिरिक्त स्थान की आवश्यकता होती है। उस स्थान की मात्रा और वितरण कार्यान्वयन पर निर्भर करेगा। कागज में आवश्यक सरणी का आकार (1 + ε)n है,लेकिन ε को चुनने के बारे में कोई और अनुशंसा नहीं की गई है। इसके अलावा, यह न तो अनुकूली है और न ही स्थिर है। उच्च-संभावना समय सीमा की गारंटी देने के लिए, इसे इनपुट को यादृच्छिक रूप से क्रमबद्ध करना होगा, जो समान तत्वों के सापेक्ष क्रम को बदलता है और किसी भी निर्धारित इनपुट को बदल देता है। साथ ही, एल्गोरिदम प्रत्येक तत्व के लिए सम्मिलन बिंदु खोजने के लिए बाइनरी खोज का उपयोग करता है, जो निर्धारित इनपुट का लाभ नहीं लेता है।

एक और दोष यह है कि इसे ऑनलाइन एल्गोरिदम के रूप में नहीं चलाया जा सकता है, क्योंकि इनपुट को यादृच्छिक रूप से फेरबदल करना संभव नहीं है। यदि इस फेरबदल के बिना उपयोग किया जाए, तो यह आसानी से द्विघात व्यवहार में परिवर्तित हो सकता है।

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

कार्यान्वयन

एल्गोरिदम

मान लीजिए कि हमारे पास n तत्वों की एक सरणी है। हम वह अंतर चुनते हैं जो हम देना चाहते हैं। तब हमारे पास आकार (1 + ε)n की एक अंतिम सरणी होगी। एल्गोरिदम लॉग एन राउंड में काम करता है। प्रत्येक राउंड में हम उतने ही तत्व सम्मिलित करते हैं जितने अंतिम एरे में हैं, एरे को पुनः संतुलित करने से पहले। डालने की स्थिति का पता लगाने के लिए, हम अंतिम सरणी में बाइनरी सर्च लागू करते हैं और तब तक निम्नलिखित तत्वों को स्वैप करते हैं जब तक कि हम खाली स्थान पर नहीं पहुंच जाते। एक बार राउंड ख़त्म होने के बाद, हम प्रत्येक तत्व के बीच रिक्त स्थान डालकर अंतिम सरणी को फिर से संतुलित करते हैं।

एल्गोरिथम के तीन महत्वपूर्ण चरण निम्नलिखित हैं:

1. बाइनरी सर्च: पहले से डाले गए तत्वों के भीतर बाइनरी सर्च लागू करके सम्मिलन की स्थिति का पता लगाना। यदि आप मध्य तत्व में खाली स्थान पर पहुंचते हैं तो यह सरणी के बाईं या दाईं ओर रैखिक रूप से जाकर किया जा सकता है।
2. सम्मिलन: तत्व को पाई गई स्थिति में सम्मिलित करना और निम्नलिखित तत्वों को 1 स्थिति से तब तक स्वैप करना जब तक कोई खाली स्थान न मिल जाए। यह उच्च संभावना के साथ लघुगणकीय समय में किया जाता है।
3. पुनः संतुलन: सरणी में तत्वों की प्रत्येक जोड़ी के बीच रिक्त स्थान डालना। पुनर्संतुलन की लागत पहले से डाले गए तत्वों की संख्या में रैखिक है। जैसे-जैसे ये लंबाई प्रत्येक दौर के लिए 2 की शक्तियों के साथ बढ़ती है, पुनर्संतुलन की कुल लागत भी रैखिक होती है।

छद्मकोड

प्रक्रिया पुनर्संतुलन (ए, प्रारंभ, अंत) है
    आर ← अंत
    w ← अंत × 2

    जबकि r ≥ आरंभ करें
        ए[डब्ल्यू] ← ए[आर]
        ए[डब्ल्यू-1] ← गैप
        आर ← आर − 1
        डब्ल्यू ← डब्ल्यू − 2

प्रक्रिया सॉर्ट (ए) है
    n ← लंबाई(ए)
    एस ← एन अंतराल की नई सरणी

    i ← 1 से मंजिल तक (log2(n-1)) करें
        पुनर्संतुलन(एस, 1, 2^(आई-1)))
        j ← 2^(i-1) से 2^i के लिए
            इन्स ← बाइनरी सर्च(ए[जे], एस, 2^आई)
            S[ins] पर A[j] डालें

यहाँ, binarysearch(el, A, k) पहले में बाइनरी खोज करता है k घटक A, रिक्त स्थान को पार करते हुए, एक ऐसा स्थान ढूंढें जहां तत्व का पता लगाया जा सके el. सम्मिलन को भरे हुए तत्वों पर अंतराल का पक्ष लेना चाहिए।

बाहरी संबंध

• Gapped Insertion Sort