C++で実装する再帰バブルソート：プログラムと仕組みをわかりやすく解説

バブルソートは、隣接する2つの要素を比較し、順序が正しくない場合に入れ替え（スワップ）を行うことで配列を整列させる基本的なソートアルゴリズムです。この記事で紹介するのはその再帰版で、自分自身を呼び出す「再帰関数」を使ってソートを実現します。

入力：5 3 4 2 1
出力：1 2 3 4 5

アルゴリズムの流れ

再帰的なバブルソートでは、以下の手順で処理が進みます。

1. 1回のパスで配列を先頭から走査し、隣接する要素を比較します。
2. 前の要素が次の要素より大きければ、両者を入れ替えます。
3. パスが終わると、最も大きい要素が配列の末尾に確定します。
4. その後、関数が自分自身を呼び出し、未整列の部分（要素数を1減らした範囲）に対して同じ処理を繰り返します。
5. 残りの要素数が1以下になった時点で再帰を終了し、配列全体が昇順に整列されます。

C++での実装例

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    if (n - 1 > 1) {
        bubbleSort(arr, n - 1);
    }
}

int main() {
    int arr[] = { 5, 3, 4, 2, 1 };
    int n = 5;
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "\t";
    }
    return 0;
}

コードのポイント

• 比較と交換：forループ内で隣接する要素 arr[i] と arr[i + 1] を比較し、順序が逆であれば一時変数 temp を使って入れ替えます。
• 再帰の終了条件：if (n - 1 > 1) により、未整列部分が2要素以上ある間だけ自分自身を再度呼び出します。この条件がないと無限再帰に陥るため非常に重要です。
• 計算量：平均・最悪ケースともに時間計算量は O(n²) です。また再帰呼び出しの深さも O(n) になるため、大きな配列を扱う際はスタックオーバーフローに注意が必要です。

まとめ

再帰版のバブルソートは、反復処理（ループ）を再帰呼び出しに置き換えたものであり、動作原理自体は通常のバブルソートとまったく同じです。アルゴリズムや再帰の理解を深める学習目的には最適ですが、実務の開発では std::sort のような効率的な標準ライブラリを利用するのが一般的です。