【C言語】再帰的バブルソートのプログラムと実装方法を解説

バブルソートとは

バブルソートは、隣り合う要素同士を比較しながらデータを整列させる、最も基本的なソートアルゴリズムの一つです。すべての要素を複数回のパス（周回）に分けて比較し、1回目のパスで最大値を末尾に配置し、2回目のパスで2番目に大きい値を後ろから2番目の位置へ、という具合に、リスト全体が完全に整列するまで処理を繰り返します。
本記事では、このバブルソートを再帰呼び出しを使って実装するC言語のプログラムを、動作の流れや具体例とあわせてわかりやすく解説します。

バブルソートのアルゴリズム

• int arr[5] = { 5, 4, 2, 1, 3 };
  int i, j;
• i = 0 から i<配列サイズ まで走査する
  • j = 0 から 配列サイズ − i − 1 まで走査する
  • 隣接する要素を比較し、前の要素が大きければ交換する
• 終了

再帰的バブルソートの考え方

• 配列の長さが1であれば、そのまま処理を終了して返す（ベースケース）
• 配列を一度だけ走査し、最大の要素を末尾に固定する
• 末尾の要素を除いた残りの部分に対して、上記の手順を再帰的に実行する

実行例

入力：Arr[] = { 5, 7, 2, 3, 1, 4 }、長さ = 6

出力：ソート済み配列：1 2 3 4 5 7

説明：

第1パス
5 7 2 3 1 4 → 交換 → 5 2 7 3 1 4
5 2 7 3 1 4 → 交換 → 5 2 3 7 1 4
5 2 3 7 1 4 → 交換 → 5 2 3 1 7 4
5 2 3 1 7 4 → 交換 → 5 2 3 1 4 7
第2パス
5 2 3 1 4 7 → 交換 → 2 5 3 1 4 7
2 5 3 1 4 7 → 交換 → 2 3 5 1 4 7
2 3 5 1 4 7 → 交換 → 2 3 1 5 4 7
2 3 1 5 4 7 → 交換 → 2 3 1 4 5 7
第3パス
2 3 1 4 5 7 → 交換 → 2 1 3 4 5 7
2 1 3 4 5 7 交換なし
第4パス
2 1 3 4 5 7 → 交換 → 1 2 3 4 5 7
1 2 3 4 5 7 以降の反復では交換なし

入力：Arr[] = { 1, 2, 3, 3, 2 }

出力：ソート済み配列：1 2 2 3 3

説明：

第1パス
1 2 3 3 2 → 交換 → 1 2 3 2 3
1 2 3 2 3 → 交換 → 1 2 2 3 3
1 2 2 3 3 以降の反復では交換なし
第2パス
1 2 2 3 3 以降の反復では交換なし

プログラムで使用するアプローチ

再帰版バブルソートでは、ベースケースを「配列の長さが1」とします。それ以外の場合は、単一のforループで配列を走査し、条件に応じて要素を交換していきます。具体的な手順は以下の通りです。

• 入力配列 Arr[] と、その要素数である長さを受け取る。
• 関数 recurbublSort(int arr[], int len) が配列とその長さを受け取り、バブルソートによって再帰的に整列を行う。
• 交換用の変数 temp を用意する。
• 配列の長さが1であれば、void としてそのまま返す。
• そうでなければ、単一のforループで配列を走査し、各要素について arr[i]>arr[i+1] が成り立てば2つの要素を交換する。
• temp=arr[i]、arr[i]=arr[i+1]、arr[i+1]=temp の順に代入して値を入れ替える。
• 直前のループで最大の要素が末尾の位置に移動しているため、長さ len を1減らす。
• recurbublSort(arr, len) を再帰的に呼び出す。
• すべての呼び出しが完了し、len が1になった時点で再帰を抜け、配列は整列済みとなる。
• main 関数の中で整列済みの配列を出力する。

Cプログラム例

#include <stdio.h>
void recurbublSort(int arr[], int len){
    int temp;

    if (len == 1){
        return;
    }
    for (int i=0; i<len-1; i++){
        if (arr[i] > arr[i+1]){
            temp=arr[i];
            arr[i]=arr[i+1];
            arr[i+1]=temp;
        }
    }
    len=len-1;
    recurbublSort(arr, len);
}
int main(){
    int Arr[] = {21, 34, 20, 31, 78, 43, 66};
    int length = sizeof(Arr)/sizeof(Arr[0]);

    recurbublSort(Arr, length);

    printf("Sorted array : ");
    for(int i=0;i<length;i++){
        printf("%d ",Arr[i]);
    }

    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Sorted array: 20 21 31 34 43 66 78

計算量について

バブルソートの平均計算量・最悪計算量はいずれも O(n²) です。また、この再帰実装では再帰呼び出しの深さが配列の長さに比例するため、スタック領域として O(n) の空間計算量が必要になります。要素数が多い場合は、通常のループによる実装や、より高速なクイックソート・マージソートなどの検討もおすすめです。