C++ में ग्नोम सॉर्ट प्रोग्राम

ग्नोम सॉर्ट क्या है?

यहां हम देखेंगे कि ग्नोम सॉर्ट कैसे काम करता है। यह एक और सॉर्टिंग एल्गोरिदम है। इस दृष्टिकोण में यदि सूची पहले से सॉर्टेड है तो यह O(n) समय लेता है। इसलिए सर्वश्रेष्ठ स्थिति समय जटिलता O(n) है। लेकिन औसत स्थिति और सबसे खराब स्थिति जटिलता O(n²) है।

एल्गोरिदम

gnomeSort(arr, n):
Begin
    index := 0
    while index < n:
        if index == 0:
            index := index + 1
        end if
        if arr[index] >= arr[index - 1]:
            index := index + 1
        else:
            exchange arr[index] and arr[index - 1]
            index := index - 1
        end if
    done
End

कैसे काम करता है

ग्नोम सॉर्ट (स्टुपिड सॉर्ट के रूप में भी जाना जाता है) एक बगीचे के ग्नोम की तरह काम करता है जो फूलों के गमलों को सॉर्ट करता है:

1. पहले तत्व से शुरू करें
2. यदि वर्तमान तत्व पिछले से बड़ा या बराबर है, तो आगे बढ़ें
3. यदि छोटा है, तो स्वैप करें और एक कदम पीछे जाएं
4. शुरुआत में पहुंचने पर आगे बढ़ें
5. अंत तक पहुंचने तक दोहराएं

उदाहरण

#include <iostream>
#include <algorithm>
using namespace std;

void gnomeSort(int arr[], int n) {
    int index = 0;
    while(index < n) {
        if(index == 0) {
            index++;
        }
        if(arr[index] >= arr[index - 1]) {
            index++;
        } else {
            swap(arr[index], arr[index - 1]);
            index--;
        }
    }
}

int main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data) / sizeof(data[0]);

    cout << "Sorted Sequence: ";
    gnomeSort(data, n);

    for(int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
    cout << endl;
    return 0;
}

आउटपुट

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

चरण-दर-चरण ट्रेस (सरणी: 3, 2, 1)

जटिलता विश्लेषण

विशेषताएं

• इन-प्लेस सॉर्टिंग
• स्थिर (स्टेबल) सॉर्ट
• कोई नेस्टेड लूप नहीं - सिंगल लूप वेरिएबल
• लगभग सॉर्टेड सरणियों के लिए अनुकूली
• इन्सर्शन सॉर्ट के समान लेकिन अलग नियंत्रण प्रवाह