साइकिल सॉर्ट

साइकिल सॉर्ट एक इन-प्लेस सॉर्टिंग एल्गोरिदम है। यह एक कंपेरिजन बेस्ड सॉर्ट भी है और किसी भी अन्य इन-प्लेस सॉर्टिंग तकनीक के लिए कुशल है। यह सॉर्टिंग कार्यों को करने के लिए मेमोरी राइट की न्यूनतम संख्या ढूंढता है।

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

• टाइम कॉम्प्लेक्सिटी: O(n^2)
• स्पेस कॉम्प्लेक्सिटी: O(1)

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

इनपुट: अनसॉर्टेड डेटा की लिस्ट: 23 63 98 74 20 14 36 45 99 78
आउटपुट: सॉर्टिंग से पहले ऐरे: 23 63 98 74 20 14 36 45 99 78
सॉर्टिंग के बाद ऐरे: 14 20 23 36 45 63 74 78 98 99

एल्गोरिदम

cycleSort(array, size)

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

Begin
    for start := 0 to n - 2 do
        key := array[start]
        location := start
        for i := start + 1 to n - 1 do
            if array[i] < key then
                location := location + 1
            done
        if location = start then
            निचले भाग को इग्नोर करें, अगले इटरेशन के लिए जाएं
        while key = array[location] do
            location := location + 1
        done
        if location ≠ start then
            swap array[location] with key
        while location ≠ start do
            location := start
            for i := start + 1 to n - 1 do
                if array[i] < key then
                    location := location + 1
                done
            while key = array[location]
                location := location + 1
            if key ≠ array[location]
                swap array[location] and key
            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 cycleSort(int *array, int n) {
    for(int start = 0; start < n - 1; start++) {
        // ऐरे एलिमेंट को सही जगह पर रखें
        int key = array[start];
        int location = start;
        for(int i = start + 1; i < n; i++) { // key के दाईं ओर छोटे एलिमेंट गिनें
            if(array[i] < key)
                location++;
        }
        if(location == start) // जब यह सही जगह पर हो तो अगले इटरेशन के लिए जाएं
            continue;
        while(key == array[location]) // यदि समान डेटा मिले तो लोकेशन बढ़ाएं
            location++;
        if(location != start)
            swapping(array[location], key);
        while(location != start) {
            location = start;
            for(int i = start + 1; i < n; i++) { // एलिमेंट रखने की लोकेशन
                if(array[i] < key)
                    location++;
            }
            while(key == array[location]) // यदि समान डेटा मिले तो लोकेशन बढ़ाएं
                location++;
            if(key != array[location])
                swapping(key, array[location]);
        }
    }
}

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);
    cycleSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 23 63 98 74 20 14 36 45 99 78
सॉर्टिंग से पहले ऐरे: 23 63 98 74 20 14 36 45 99 78
सॉर्टिंग के बाद ऐरे: 14 20 23 36 45 63 74 78 98 99