उदाहरण के साथ शेल सॉर्ट एल्गोरिथ्म

शेल सॉर्ट क्या है?

शेल की विधि, या डेटा संरचना में शेल सॉर्ट, एक कुशल इन-प्लेस तुलना सॉर्ट एल्गोरिथ्म है। इसका नाम डोनाल्ड शेल के नाम पर रखा गया है जब उन्होंने 1959 में प्रारंभिक विचार प्रस्तुत किया था। शेल सॉर्ट, इंसर्शन सॉर्ट एल्गोरिथ्म का एक सामान्यीकृत विस्तार है।

इस सॉर्टिंग एल्गोरिदम का मूल विचार उन तत्वों को समूहीकृत करना है जो दूर-दूर हैं और उन्हें तदनुसार सॉर्ट करना है। फिर धीरे-धीरे उनके बीच के अंतर को कम करें। शेल सॉर्ट उन तत्वों की तुलना और आदान-प्रदान करके सम्मिलन सॉर्ट की औसत केस समय जटिलता को दूर करता है जो दूर हैं।

यह अंतर, जिसे अंतराल के रूप में जाना जाता है, कुछ इष्टतम अंतराल अनुक्रमों के अनुसार कम हो जाता है। शेल सॉर्ट का चलने का समय भी इन अनुक्रमों पर निर्भर करता है। कई अंतराल अनुक्रम हैं, जैसे शेल का मूल अनुक्रम, नूथ का सूत्र, हिबर्ड की वृद्धि, आदि। शेल का मूल अंतराल अनुक्रम है - n/2, n/4, n/8, ……….1

शेल सॉर्ट एल्गोरिथ्म

शेल सॉर्ट एल्गोरिथ्म के लिए चरण या प्रक्रिया इस प्रकार है-

चरण 1) अंतराल मान को आरंभ करें, h = n/2. (इस उदाहरण में, n सरणी का आकार है)

चरण 2) अंतराल h की दूरी के भीतर सभी तत्वों को एक उप-सूची में रखें।

चरण 3) सम्मिलन क्रम का उपयोग करके उन उप-सूचियों को क्रमबद्ध करें।

चरण 4) नया अंतराल सेट करें, h=h/2.

चरण 5) यदि h>0 है, तो चरण 2 पर जाएँ। अन्यथा चरण 6 पर जाएँ।

चरण 6) परिणामी आउटपुट क्रमबद्ध सरणी होगी।

शेल सॉर्ट कैसे काम करता है

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

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

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

शैल सॉर्ट कार्य

शेल सॉर्ट एल्गोरिथ्म का कार्य

आइए शेल सॉर्ट एल्गोरिथ्म का एक निम्न उदाहरण देखें। इस उदाहरण में, हम शेल सॉर्ट का उपयोग करके निम्नलिखित सरणी को सॉर्ट करेंगे:

शेल सॉर्ट एल्गोरिथ्म का कार्य

चरण 1) यहाँ, सारणी का आकार 8 है। इस प्रकार, अंतराल मान h = 8/2 या 4 होगा।

चरण 2) अब, हम सभी तत्वों को 4 की दूरी पर संग्रहीत करेंगे। हमारे मामले में, उपसूचियाँ हैं - {8, 1}, {6, 4}, {7, 5}, {2, 3}।

शेल सॉर्ट एल्गोरिथ्म का कार्य

चरण 3) अब, उन उपसूचियों को सम्मिलन क्रम का उपयोग करके क्रमबद्ध किया जाएगा, जहां दोनों संख्याओं की तुलना करने और तदनुसार क्रमबद्ध करने के लिए एक अस्थायी चर का उपयोग किया जाता है।

स्वैपिंग ऑपरेशन के बाद सरणी निम्नलिखित जैसी होगी-

शेल सॉर्ट एल्गोरिथ्म का कार्य

चरण 4) अब हम अंतराल के प्रारंभिक मान को घटा देंगे। नया अंतराल h=h/2 या 4/2 या 2 होगा।

चरण 5) चूंकि 2>0 है, हम सभी तत्वों को 2 की दूरी पर संग्रहीत करने के लिए चरण 2 पर जाएंगे। इस समय के लिए, उपसूचियाँ हैं-

{1, 5, 8, 7}, {4, 2, 6, 3}

शेल सॉर्ट एल्गोरिथ्म का कार्य

फिर इन सबलिस्ट को इन्सर्टेशन सॉर्ट का उपयोग करके सॉर्ट किया जाएगा। पहली सबलिस्ट की तुलना और अदला-बदली करने के बाद, सरणी निम्नलिखित होगी।

शेल सॉर्ट एल्गोरिथ्म का कार्य

दूसरी उपसूची को क्रमबद्ध करने के बाद, मूल सारणी होगी:

शेल सॉर्ट एल्गोरिथ्म का कार्य

फिर से, अंतराल कम हो जाएगा। अब अंतराल h=h/2 या 2/1 या 1 होगा। इसलिए हम संशोधित सरणी को सॉर्ट करने के लिए सम्मिलन सॉर्ट एल्गोरिथ्म का उपयोग करेंगे।

निम्नलिखित में सम्मिलन सॉर्ट का चरण-दर-चरण प्रक्रियात्मक चित्रण है।

शेल सॉर्ट एल्गोरिथ्म का कार्य

शेल सॉर्ट एल्गोरिथ्म का कार्य

शेल सॉर्ट एल्गोरिथ्म का कार्य

अंतराल को पुनः 2 से विभाजित किया जाता है। इस समय तक, अंतराल 0 हो जाता है। अतः हम चरण 6 पर जाते हैं।

चरण 6) चूंकि अंतराल 0 है, इसलिए सरणी को इस समय के अनुसार क्रमबद्ध किया जाता है। क्रमबद्ध सरणी है-

शेल सॉर्ट एल्गोरिथ्म का कार्य

छद्म कोड

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

सी/सी में शेल सॉर्ट प्रोग्रामC++

इनपुट:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

आउटपुट:

Sorted Output:

1 2 3 4 5 6 7 8

शैल सॉर्ट उदाहरण Python

इनपुट:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

आउटपुट:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

शैल सॉर्ट के अनुप्रयोग

शेल सॉर्ट के महत्वपूर्ण अनुप्रयोग इस प्रकार हैं:

  • शैल सॉर्ट का प्रयोग किया जाता है लिनक्स कर्नेल क्योंकि यह कॉल स्टैक का उपयोग नहीं करता है.
  • uClibc लाइब्रेरी शेल सॉर्ट का उपयोग करती है।
  • bzip2 कंप्रेसर अत्यधिक पुनरावृत्ति को रोकने के लिए शेल सॉर्ट का उपयोग करता है।

शैल सॉर्ट के लाभ और नुकसान

फायदे नुकसान
किसी स्टैक कॉल की आवश्यकता नहीं है. विशाल सरणी आकार के लिए कुशल नहीं है।
आसान कार्यान्वयन. व्यापक रूप से फैले तत्वों के लिए अकुशल।
कम दूरी पर स्थित तत्वों के लिए कुशल।

शैल सॉर्ट जटिलता विश्लेषण

शेल सॉर्ट की समय जटिलता

शेल सॉर्ट एल्गोरिथ्म की समय जटिलता O(n^2) है। तर्क इस प्रकार है:

सर्वोत्तम स्थिति के लिए, जब सरणी को पहले से व्यवस्थित किया गया था, तो सभी अंतरालों के लिए परीक्षणों की कुल मात्रा लॉग एन के बराबर होगी। इस प्रकार जटिलता O(n*log n) होगी।

सबसे खराब स्थिति के लिए, मान लें कि सरणी इस तरह से बनी है कि तत्वों को सबसे ज़्यादा तुलना की ज़रूरत है। तब सभी तत्वों की तुलना नहीं की जाएगी और अंतिम पुनरावृत्ति तक स्विच नहीं किया जाएगा। इसलिए, अंतिम वृद्धि के लिए आवश्यक कुल तुलना O(n^2) है।

निष्कर्ष में, समय जटिलताएं होंगी

  1. सर्वोत्तम स्थिति जटिलता: O(n*log n)
  2. औसत केस जटिलता: O(n*log n)
  3. सबसे खराब स्थिति जटिलता: O(n^2)

शेल सॉर्ट की रनिंग टाइम जटिलता काफी हद तक इस्तेमाल किए गए गैप इंक्रीमेंट अनुक्रमों पर निर्भर करती है। हालाँकि, शेल सॉर्ट के लिए सबसे अच्छा इंक्रीमेंट अनुक्रम अभी भी अज्ञात है।

शैल सॉर्ट स्पेस जटिलता

इस तुलना सॉर्ट में, हमें किसी अतिरिक्त सहायक स्थान की आवश्यकता नहीं है। इस प्रकार इस तरह के एल्गोरिदम की स्पेस जटिलता O(1) है।