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

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


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

कॉकटेल सॉर्ट बबल सॉर्ट का एक और प्रकार है। बबल सॉर्ट तकनीक में, यह हमेशा बाएं से दाएं खोजता है, और अंत में सबसे बड़ा तत्व ढूंढता है, दूसरे चरण में यह दूसरा सबसे बड़ा तत्व दूसरे अंतिम स्थान पर ढूंढता है। यह सॉर्टिंग तकनीक वैकल्पिक रूप से दोनों दिशाओं में पार करती है।

एल्गोरिदम

cocktail(array, n):
Begin
    flag := true
    start := 0, end := n-1
    while flag is set:
        flag := false
        for i in range start to end-1:
            if arr[i] > arr[i+1]:
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        if flag is not set:
            break
        end if
        flag := false
        end := end - 1
        for i in range end-1 down to start:
            if arr[i] > arr[i+1]:
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        start := start + 1
    done
End

उदाहरण

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

void cocktailSort(int arr[], int n) {
    bool flag = true;
    int start = 0, end = n - 1;

    while(flag) {
        flag = false;

        // बाएं से दाएं (बबल सॉर्ट की तरह)
        for(int i = start; i < end; i++) {
            if(arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }

        if(!flag) {
            break;  // यदि कुछ नहीं बदला, तो लूप तोड़ें
        }

        flag = false;
        end--;  // अंत पॉइंटर घटाएं

        // दाएं से बाएं
        for(int i = end - 1; i >= start; i--) {
            if(arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        start++;
    }
}

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

    cout << "Sorted Sequence: ";
    cocktailSort(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

कैसे काम करता है (चरण-दर-चरण)

प्रारंभिक: [54, 74, 98, 154, 98, 32, 20, 13, 35, 40]

पास 1 (फॉरवर्ड): सबसे बड़ा 154 अंत में जाता है
[54, 74, 98, 98, 32, 20, 13, 35, 40, 154]

पास 1 (बैकवर्ड): सबसे छोटा 13 शुरुआत में जाता है
[13, 54, 74, 98, 98, 32, 20, 35, 40, 154]

पास 2 (फॉरवर्ड): अगला सबसे बड़ा 98...
[13, 54, 74, 98, 32, 20, 35, 40, 98, 154]

पास 2 (बैकवर्ड): अगला सबसे छोटा 20...
[13, 20, 54, 74, 98, 32, 35, 40, 98, 154]

... जारी रहता है जब तक सॉर्ट न हो जाए

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

स्थिति समय जटिलता स्थान जटिलता
सर्वश्रेष्ठ O(n) O(1)
औसत O(n²) O(1)
सबसे खराब O(n²) O(1)

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

विशेषता बबल सॉर्ट कॉकटेल सॉर्ट
दिशा एक दिशा (बाएं→दाएं) द्विदिशात्मक
कछुआ समस्या हां आंशिक रूप से हल
सर्वश्रेष्ठ स्थिति O(n) O(n)
स्थिरता स्थिर स्थिर

अन्य नाम

  • द्विदिशात्मक बबल सॉर्ट
  • कॉकटेल शेकर सॉर्ट
  • शेकर सॉर्ट
  • रिपल सॉर्ट
  • शटल सॉर्ट
  1. C++ में पिरामिड के आयतन का प्रोग्राम C++ में पिरामिड के आयतन का प्रोग्राम

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

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

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

  1. पायथन प्रोग्राम: कॉकटेल सॉर्ट पायथन प्रोग्राम: कॉकटेल सॉर्ट

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