再帰的アプローチによるバブルソートのC++プログラム

この記事では、古典的なソートアルゴリズムであるバブルソートを、再帰（リカーシブ）を用いた別のアプローチで実装する方法を解説します。一般的なバブルソートはfor文などの反復処理で記述されることが多いですが、ここでは同じ処理を再帰呼び出しで表現してみましょう。

再帰バブルソートの仕組み

再帰版バブルソートでは、関数を1回呼び出すたびに配列全体を走査する「1パス」が実行され、その時点での最大の要素が配列の末尾に移動します。その後、問題のサイズを1つ減らして（n-1）自分自身を再度呼び出します。そして、nが1になった時点で、それ以上ソートすべき要素が存在しないため、再帰を終了します。

アルゴリズム

bubbleRec(arr, n)

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

手順を日本語でまとめると以下の通りです。

• nが1なら何もせずに戻る（ベースケース）
• 隣接する要素同士を比較し、順序が逆であれば入れ替える
• 配列のサイズを1減らして、再帰的にbubbleRecを呼び出す

C++での実装例

#include<iostream>
using namespace std;
void recBubble(int arr[], int n){
    if (n == 1)
        return;                    // ベースケース：要素数が1なら終了
    for (int i=0; i<n-1; i++)      // 各パスの走査
        if (arr[i] > arr[i+1])     // 現在の要素が次の要素より大きければ
            swap(arr[i], arr[i+1]); // 要素を交換する
    recBubble(arr, n-1);           // サイズを1減らして再帰呼び出し
}
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] << " ";
    }
}

実行結果

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

計算量について

このアルゴリズムの時間計算量は、最悪・平均ともにO(n²)であり、反復版バブルソートと同等です。空間計算量については、再帰呼び出しごとにスタック領域を消費するためO(n)となります。そのため、大きなデータセットに対しては、反復版やより効率的なソートアルゴリズム（クイックソート、マージソートなど）を選ぶのが一般的です。ただし、再帰の考え方を学ぶ教材としては非常に良い題材といえるでしょう。