कॉम्ब सॉर्ट

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

कॉम्ब सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: बेस्ट केस के लिए O(n log n)। औसत केस के लिए O(n^2/2^p) (p इंक्रीमेंट की संख्या है) और सबसे खराब केस के लिए O(n^2)।
• स्पेस कॉम्प्लेक्सिटी: O(1)

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

इनपुट: अनसॉर्टेड डेटा की लिस्ट: 108 96 23 74 12 56 85 42 13 47
आउटपुट: सॉर्टिंग से पहले ऐरे: 108 96 23 74 12 56 85 42 13 47
सॉर्टिंग के बाद ऐरे: 12 13 23 42 47 56 74 85 96 108

एल्गोरिदम

CombSort(array, size)

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

Begin
    gap := size
    flag := true
    while gap ≠ 1 OR flag = true do
        gap = floor(gap / 1.3) // विभाजन के बाद फ्लोर वैल्यू
        if gap < 1 then
            gap := 1
        flag = false
        for i := 0 to size - gap - 1 do
            if array[i] > array[i + gap] then
                swap array[i] with array[i + gap]
                flag = true
            done
        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; // श्रिंक फैक्टर द्वारा गैप को कम करें
        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 << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    combSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 108 96 23 74 12 56 85 42 13 47
सॉर्टिंग से पहले ऐरे: 108 96 23 74 12 56 85 42 13 47
सॉर्टिंग के बाद ऐरे: 12 13 23 42 47 56 74 85 96 108