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

रिकर्सिव बबल सॉर्ट क्या है?

इस खंड में हम प्रसिद्ध बबल सॉर्ट तकनीक के दूसरे दृष्टिकोण को देखेंगे। हमने बबल सॉर्ट का उपयोग इटरेटिव तरीके से किया है। लेकिन यहां हम बबल सॉर्ट के रिकर्सिव दृष्टिकोण को देखेंगे।

एल्गोरिदम

bubbleRec(arr, n):
begin
    if n == 1, return
    for i in range 0 to n-2:
        if arr[i] > arr[i+1]:
            exchange arr[i] and arr[i+1]
        end if
    done
    bubbleRec(arr, n-1)
end

उदाहरण

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

void recBubble(int arr[], int n) {
    // बेस केस
    if (n == 1)
        return;

    // एक पास: सबसे बड़ा तत्व अंत में बबल अप होगा
    for (int i = 0; i < n-1; i++) {
        if (arr[i] > arr[i+1]) {
            swap(arr[i], arr[i+1]);
        }
    }

    // शेष n-1 तत्वों के लिए पुनरावृत्ति
    recBubble(arr, n-1);
}

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

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

कैसे काम करता है

1. बेस केस: यदि n == 1, सरणी पहले से सॉर्टेड है
2. रिकर्सिव केस: एक पास पूरा करें (सबसे बड़ा तत्व अंत में जाता है), फिर पहले n-1 तत्वों पर पुनरावृत्ति करें
3. प्रत्येक रिकर्सिव कॉल समस्या का आकार 1 से कम करती है

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

इटरेटिव बनाम रिकर्सिव

ऑप्टिमाइज़ेशन: अर्ली टर्मिनेशन

void recBubbleOptimized(int arr[], int n) {
    if (n == 1) return;

    bool swapped = false;
    for (int i = 0; i < n-1; i++) {
        if (arr[i] > arr[i+1]) {
            swap(arr[i], arr[i+1]);
            swapped = true;
        }
    }

    // यदि कोई स्वैप नहीं हुआ, तो सरणी सॉर्टेड है
    if (!swapped) return;

    recBubbleOptimized(arr, n-1);
}