Chương trình C++ cho Bubble Sort đệ quy (Recursive Bubble Sort)

Bubble Sort đệ quy: tiếp cận đệ quy cho thuật toán Bubble Sort nổi tiếng. Thay vì lặp lồng nhau, dùng đệ quy để giảm kích thước mảng cần xét sau mỗi pass.

Thuật toán

bubbleRec(arr, n):
    if n == 1: return
    for i = 0 to n-2:
        if arr[i] > arr[i+1]: swap(arr[i], arr[i+1])
    bubbleRec(arr, n-1)
end

Code ví dụ

#include <iostream>
using namespace std;

void recBubble(int arr[], int n) {
    if (n == 1) return;           // Base case
    
    for (int i = 0; i < n-1; i++) // Một pass bubble sort
        if (arr[i] > arr[i+1])
            swap(arr[i], arr[i+1]);
    
    recBubble(arr, n-1);          // Đệ quy cho n-1 phần tử đầu
}

int main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    
    cout << "Day truoc: ";
    for(int x : data) cout << x << " ";
    
    recBubble(data, n);
    
    cout << "\nDay sau:  ";
    for(int x : data) cout << x << " ";
    return 0;
}

Kết quả

Day truoc: 54 74 98 154 98 32 20 13 35 40
Day sau:  13 20 32 35 40 54 74 98 98 154

Phân tích

• Độ phức tạp thời gian: O(n²) - giống bubble sort lặp.
• Độ phức tạp không gian: O(n) do call stack đệ quy (bubble sort lặp là O(1)).
• Ưu điểm: Code ngắn gọn, dễ hiểu bản chất đệ quy.
• Nhược điểm: Tốn stack, chậm hơn do overhead gọi hàm, dễ stack overflow nếu n lớn.

So sánh

Khi nào dùng?

Chỉ dùng cho mục đích học tập, hiểu đệ quy. Thực tế luôn dùng phiên bản lặp hoặc thuật toán tốt hơn (QuickSort, MergeSort, std::sort).