शेल सॉर्ट

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

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

• टाइम कॉम्प्लेक्सिटी: बेस्ट केस के लिए O(n log n), और अन्य मामलों के लिए यह गैप सीक्वेंस पर निर्भर करता है।
• स्पेस कॉम्प्लेक्सिटी: O(1)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड लिस्ट: 23 56 97 21 35 689 854 12 47 66
आउटपुट: सॉर्टिंग से पहले ऐरे: 23 56 97 21 35 689 854 12 47 66
सॉर्टिंग के बाद ऐरे: 12 21 23 35 47 56 66 97 689 854

एल्गोरिदम

shellSort(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या
आउटपुट: सॉर्टेड ऐरे

Begin
    for gap := size / 2, जब gap > 0 और gap को gap / 2 से अपडेट किया जाता है do
        for j := gap to size - 1 do
            for k := j - gap to 0, gap वैल्यू से घटाएं do
                if array[k + gap] >= array[k]
                    break
                else
                    swap array[k + gap] with array[k]
            done
        done
    done
End

उदाहरण

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    // a और b की सामग्री को स्वैप करें
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void shellSort(int *arr, int n) {
    int gap, j, k;
    for(gap = n / 2; gap > 0; gap = gap / 2) {
        // प्रारंभ में gap = n/2, gap/2 से घट रहा है
        for(j = gap; j < n; j++) {
            for(k = j - gap; k >= 0; k -= gap) {
                if(arr[k + gap] >= arr[k])
                    break;
                else
                    swapping(arr[k + gap], arr[k]);
            }
        }
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    shellSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 23 56 97 21 35 689 854 12 47 66
सॉर्टिंग से पहले ऐरे: 23 56 97 21 35 689 854 12 47 66
सॉर्टिंग के बाद ऐरे: 12 21 23 35 47 56 66 97 689 854