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

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

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

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

यह अंतराल, शेल के मूल, नुथ के, हिबार्ड के या सेडगेविक के जैसे चुने हुए क्रम का अनुसरण करता है। शेल का मूल इस प्रकार है: n/2, n/4, ..., 1.

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

चरण 1) अंतराल मान h = n/2 को प्रारंभ करें, जहाँ n सरणी का आकार है।

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

चरण 3) प्रत्येक उपसूची को इंसर्शन सॉर्ट का उपयोग करके क्रमबद्ध करें।

चरण 4) एक नया अंतराल h = h/2 निर्धारित करें।

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

चरण 6) अब परिणामी ऐरे पूरी तरह से सॉर्ट किया हुआ है।

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

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

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

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

आइए नीचे दिए गए ऐरे को शेल सॉर्ट का उपयोग करके सॉर्ट करें।

चरण 1) ऐरे का आकार 8 है, इसलिए प्रारंभिक अंतराल मान h = 8/2 = 4 है।

चरण 2) समूह तत्वों को चार स्थानों के अंतराल पर रखें। उपसूचियाँ: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

चरण 3) प्रत्येक उपसूची को इंसर्शन सॉर्ट विधि का उपयोग करके क्रमबद्ध करें। तत्वों के स्थान परिवर्तन के दौरान रखे जा रहे मान को एक अस्थायी चर में रखा जाता है। अदला-बदली के बाद, सरणी इस प्रकार दिखाई देगी।

चरण 4) अंतराल को घटाएँ। नया अंतराल h = 4/2 = 2 है।

चरण 5) क्योंकि 2 > 0, चरण 2 पर वापस जाएँ और दो स्थानों के अंतर पर तत्वों को समूहित करें: {1, 5, 8, 7} और {4, 2, 6, 3}.

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

दूसरी उपसूची को क्रमबद्ध करने के बाद:

अंतराल को फिर से घटाकर h = 2/2 = 1 कर दें। एक के अंतराल के साथ, शेल सॉर्ट पूरे ऐरे पर अंतिम इंसर्शन-सॉर्ट पास चलाता है, जैसा कि नीचे दिखाया गया है।

चरण 6) अंतराल को दोबारा विभाजित करने पर 0 प्राप्त होता है। अब सरणी पूरी तरह से क्रमबद्ध है:

झूठाCode शेल सॉर्ट के लिए

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > 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]

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

शेल सॉर्ट अभी भी आधुनिक प्रणालियों में दिखाई देता है जहां स्टैक स्पेस या सरलता मायने रखती है।

• RSI लिनक्स कर्नेल यह शेल सॉर्ट का उपयोग उन जगहों पर करता है जहां कॉल स्टैक से बचना महत्वपूर्ण होता है।
• uClibc एम्बेडेड सी लाइब्रेरी मेमोरी के उपयोग को कम रखने के लिए शेल सॉर्ट का उपयोग करती है।
• ब्लॉक-सॉर्टिंग के दौरान डीप रिकर्सन से बचने के लिए bzip2 शेल सॉर्ट का उपयोग करता है।
• एम्बेडेड फर्मवेयर छोटे डेटासेट के लिए शेल सॉर्ट को प्राथमिकता देता है जहां पुनरावर्तन प्रतिबंधित होता है।

शेल सॉर्ट के फायदे और नुकसान

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

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

शेल सॉर्ट की समय जटिलता उपयोग किए गए अंतराल अनुक्रम पर निर्भर करती है।

सबसे अच्छे मामले में, जब सरणी पहले से ही लगभग व्यवस्थित होती है, तो प्रत्येक पास के लिए केवल लघुगणकीय संख्या में परीक्षणों की आवश्यकता होती है, जिससे O(n log n) प्राप्त होता है।

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

1. सर्वोत्तम स्थिति में जटिलता: O(n log n)
2. औसत जटिलता: अंतराल अनुक्रम के आधार पर O(n log n) से O(n^(4/3)) तक।
3. सबसे खराब स्थिति में जटिलता: शेल के मूल अनुक्रम के साथ O(n^2)

सर्वोत्तम सामान्य प्रयोजन अंतराल अनुक्रम अभी भी एक खुला शोध प्रश्न है, हालांकि सेडगेविक और सिउरा अनुक्रम व्यवहार में अच्छा प्रदर्शन करते हैं।

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

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

अक्सर पूछे जाने वाले प्रश्न