Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


कॉम्ब सॉर्ट क्या है?

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

जटिलता

  • सर्वश्रेष्ठ स्थिति: O(n log n)
  • औसत स्थिति: O(n²/2^p) जहां p इंक्रीमेंट की संख्या है
  • सबसे खराब स्थिति: O(n²)

एल्गोरिदम

CombSort(array, size):
Begin
    gap := size
    flag := true
    while gap != 1 OR flag == true:
        gap = floor(gap / 1.3)
        if gap < 1:
            gap := 1
        flag = false
        for i = 0 to size - gap - 1:
            if array[i] > array[i + gap]:
                swap array[i] with array[i + gap]
                flag = true
        done
    done
End

उदाहरण

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

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

void combSort(int *array, int size) {
    int gap = size;
    bool flag = true;

    while(gap != 1 || flag == true) {
        gap = (gap * 10) / 13;  // श्रिंक फैक्टर 1.3 से विभाजित
        if(gap < 1)
            gap = 1;
        flag = false;

        for(int i = 0; i < size - gap; i++) {
            if(array[i] > array[i + gap]) {
                swap(array[i], array[i + gap]);
                flag = true;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);

    combSort(arr, n);

    cout << "Array after Sorting: ";
    display(arr, n);

    return 0;
}

आउटपुट

Enter the number of elements: 10
Enter elements:
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108

गैप अनुक्रम उदाहरण (n=10)

10 → 7 → 5 → 3 → 2 → 1 → 1 → 1 ... (जब तक कोई स्वैप न हो)

कॉम्ब सॉर्ट बनाम बबल सॉर्ट

पहलू बबल सॉर्ट कॉम्ब सॉर्ट
तुलना गैप हमेशा 1 श्रिंक फैक्टर 1.3 से घटता है
कछुआ समस्या हां (छोटे तत्व धीरे-धीरे चलते हैं) नहीं (बड़े गैप से कछुए तेजी से चलते हैं)
सर्वश्रेष्ठ स्थिति O(n) O(n log n)
औसत स्थिति O(n²) O(n²/2^p)

श्रिंक फैक्टर 1.3 क्यों?

लेखकों (व्लादिमीर डोब्रीव और स्टीफन लेसी) ने अनुभवजन्य रूप से पाया कि 1.3 सबसे अच्छा प्रदर्शन देता है। 1.3 से कम → अधिक तुलनाएं, 1.3 से अधिक → कछुआ समस्या को प्रभावी ढंग से हल करने में विफल।

  1. C++ प्रोग्राम बाईसेक्शन मेथड के लिए C++ प्रोग्राम बाईसेक्शन मेथड के लिए

    फंक्शन f(x) दिया गया है जिसमें संख्या a और b हैं जहां, f(a) * f(b) > 0 और फंक्शन f(x) a और b के बीच होना चाहिए यानी f(x) = [a, b]। कार्य बाईसेक्शन मेथड का उपयोग करके फंक्शन f(x) में अंतराल a और b के बीच स्थित रूट का मान खोजना है।बाईसेक्शन मेथड क्या है?बाईसेक्शन मेथड का उपयोग फंक्शन f(x) में दिए ग

  1. C++ में पिरामिड के आयतन का प्रोग्राम C++ में पिरामिड के आयतन का प्रोग्राम

    पिरामिड के बेस के प्रकार के आधार पर भुजाएं दी गई हैं, कार्य पिरामिड का आयतन गणना करना है।पिरामिड एक 3-D आकृति है जिसकी बाहरी सतहें त्रिकोणीय हैं जो सामान्य बिंदु पर मिलती हैं जिससे पिरामिड का तीक्ष्ण किनारा बनता है। पिरामिड का आयतन उसके बेस के प्रकार पर निर्भर करता है।पिरामिड के बेस के विभिन्न प्रका

  1. C++ में क्विकसॉर्ट प्रोग्राम C++ में क्विकसॉर्ट प्रोग्राम

    क्विकसॉर्ट क्या है? क्विकसॉर्ट एक सॉर्टिंग तकनीक है जो अनसॉर्टेड सूची (सरणी) को सॉर्ट करने के लिए तुलनाओं का उपयोग करती है। क्विकसॉर्ट को पार्टीशन एक्सचेंज सॉर्ट के नाम से भी जाना जाता है। यह एक स्थिर सॉर्ट नहीं है, क्योंकि समान सॉर्ट आइटम्स का सापेक्ष क्रम संरक्षित नहीं रहता। क्विकसॉर्ट एक सरणी प