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

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

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 log n) समय (क्विकसॉर्ट की तुलना में) में चलने की उच्च संभावना दिखाई गई थी। पेपर में कोई पूर्ण कार्यान्वयन नहीं दिया गया है, न ही सम्मिलन और पुनर्संतुलन जैसे महत्वपूर्ण भागों के स्पष्ट एल्गोरिदम दिए गए हैं। लाइब्रेरी सॉर्टिंग की दक्षता वास्तविकता में अन्य सॉर्टिंग विधियों की तुलना में कैसे तुलना करती है, इस पर चर्चा करने के लिए अधिक जानकारी की आवश्यकता होगी।

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

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

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

कार्यान्वयन

एल्गोरिदम

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

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

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

बाहरी संबंध

• Gapped Insertion Sort