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

C++ में सर्कल सॉर्ट

सर्कल सॉर्ट दिए गए एरे के एलिमेंट्स को सॉर्ट करने का एक दिलचस्प सॉर्टिंग एल्गोरिदम है। एल्गोरिदम एरे के एलिमेंट्स की डायामीट्रिकली तुलना करता है और एक बार एक भाग में एलिमेंट्स सॉर्ट हो जाने पर, फिर एरे के दूसरे छोर को डायामीट्रिकली सॉर्ट करता रहता है।

उदाहरण

आइए एक एरे के लिए सर्कल सॉर्ट को विज़ुअलाइज़ करें। मान लीजिए हमारे पास 6 एलिमेंट्स वाला एक एरे है।

इनपुट:

N = 6
arr [ ] = { 2, 1, 5, 8, 7, 9 }

जब हम प्रत्येक एरे एलिमेंट के लिए कॉन्सेंट्रिक सर्कल बनाते हैं, तो यह इस प्रकार दिखाई देगा

C++ में सर्कल सॉर्ट

आउटपुट:

1 2 5 7 8 9

व्याख्या: सर्कल सॉर्ट का उपयोग करके एरे में एलिमेंट्स को सॉर्ट करने के बाद, यह 1, 2, 5, 7, 8, 9 होगा।

सर्कल सॉर्ट के लिए एल्गोरिदम

  • एरे के पहले एलिमेंट की तुलना अंतिम एलिमेंट से करें, दूसरे एलिमेंट की तुलना अंतिम से दूसरे एलिमेंट से करें।
  • अब एरे को दो हिस्सों में विभाजित करें और फिर पहले आधे के पहले एलिमेंट की तुलना उसके अंतिम एलिमेंट से करने के लिए फिर से सर्कल सॉर्ट का उपयोग करें।
  • चरण-1 और चरण-2 को पुनरावर्ती रूप से कॉल करें जब तक कि एरे सॉर्ट न हो जाए।

सर्कल सॉर्ट लागू करने के लिए C++ प्रोग्राम

उदाहरण

#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
    bool swaped = false;
    if (n <= 2) {
        if (arr[0] > arr[n - 1]) {
            swap(arr[0], arr[n - 1]);
            swaped = true;
        }
        return swaped;
    }
    int mid = (n + 1) / 2;
    for (int i = 0; i < mid; i++) {
        if (i == n - i - 1) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swaped = true;
            }
        } else {
            if (arr[i] > arr[n - i - 1]) {
                swap(arr[i], arr[n - i - 1]);
                swaped = true;
            }
        }
    }
    if (circle_sort_rec(arr, mid))
        swaped = true;
    if (circle_sort_rec(arr + mid, n - mid))
        swaped = true;
    return swaped;
}
void circle_sort(int * arr, int size) {
    while (circle_sort_rec(arr, size)) {
        ;
    }
    return;
}
int main() {
    int size = 5;
    int arr[size] = {2,1,7,4,5,9};
    circle_sort(arr, size);
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    return 0;
}

आउटपुट

1 2 4 5 7
  1. - C++ में बाइनरी इंसर्शन सॉर्ट

    बाइनरी इंसर्शन सॉर्ट इंसर्शन सॉर्ट का एक विशेष प्रकार है जो ऐरे में डाले गए एलिमेंट की सही स्थिति खोजने के लिए बाइनरी सर्च एल्गोरिदम का उपयोग करता है। इंसर्शन सॉर्ट एक सॉर्टिंग तकनीक है जो ऐरे में एलिमेंट की सही स्थिति ढूंढकर और फिर उसे उसकी सही स्थिति में डालकर काम करती है। बाइनरी सर्च एक खोज तकनीक

  1. C++ में वर्ग के परिवृत्त का क्षेत्रफल C++ में वर्ग के परिवृत्त का क्षेत्रफल

    इस समस्या में, हम वर्ग के परिवृत्त का क्षेत्रफल गणना करेंगे जब हमें वर्ग की भुजा दी गई हो। आगे बढ़ने से पहले आइए मूल परिभाषाओं को दोहराते हैं ताकि अवधारणाओं को बेहतर ढंग से समझा जा सके। वर्ग समान भुजाओं वाला एक चतुर्भुज है। परिवृत्त एक वृत्त है जो बहुभुज के सभी शीर्षों को छूता है। क्षेत्रफल किसी भी

  1. - C++ में स्ट्रैंड सॉर्ट

    इस सेक्शन में हम देखेंगे कि C++ के स्टैंडर्ड लाइब्रेरी का उपयोग करके किसी ऐरे या लिंक्ड लिस्ट को कैसे सॉर्ट कर सकते हैं। C++ में विभिन्न उद्देश्यों के लिए कई अलग-अलग लाइब्रेरीज हैं। सॉर्टिंग उनमें से एक है। C++ फ़ंक्शन std::list::sort() लिस्ट के एलिमेंट्स को आरोही क्रम में सॉर्ट करता है। समान एलिमे