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

バブルソートは、隣り合う要素を比較して並べ替える最も基本的なソートアルゴリズムの一つです。通常はfor文などのループで実装されますが、再帰呼び出しを使って実現することもできます。ここでは、Javaで再帰的にバブルソートを実装する方法を、サンプルコードとともに詳しく解説します。

再帰的バブルソートのサンプルコード

以下が、再帰処理を用いたバブルソートのJavaプログラムです。

import java.util.Arrays;
public class Demo{
    static void bubble_sort(int my_arr[], int len_arr){
        if (len_arr == 1)
            return;
        for (int i = 0; i < len_arr - 1; i++)
            if (my_arr[i] > my_arr[i+1]){
                int temp = my_arr[i];
                my_arr[i] = my_arr[i+1];
                my_arr[i+1] = temp;
            }
        bubble_sort(my_arr, len_arr - 1);
    }
    public static void main(String[] args){
        int my_arr[] = {45, 67, 89, 31, 63, 0, 21, 12};
        bubble_sort(my_arr, my_arr.length);
        System.out.println("The array after implementing bubble sort is ");
        System.out.println(Arrays.toString(my_arr));
    }
}

実行結果

The array after implementing bubble sort is
[0, 12, 21, 31, 45, 63, 67, 89]

コードの仕組み

このプログラムでは、Demo クラスの中にバブルソートを実行するメソッド bubble_sort() を定義しています。処理の流れは以下のとおりです。

• 終了条件（ベースケース）： 配列の長さが1になった時点で、それ以上ソートの必要がないため、メソッドはそのままreturnします。
• 1回のパス（走査）： 配列を先頭から順に走査し、現在の要素が次の要素より大きければ、両者を一時変数 temp を使って入れ替えます。
• 再帰呼び出し： 最初のパスが完了すると、配列内で最大の要素が末尾に確定します。そこで、残りの未整列部分に対して bubble_sort() を再度呼び出し（引数の長さを1減らす）、これを繰り返すことで全体を昇順に整列させます。

main() メソッドでは、整数型の配列を定義し、それを引数として bubble_sort() メソッドに渡しています。ソート後の結果は Arrays.toString() を使って読みやすい形式で出力されます。

計算量について

再帰的なバブルソートの計算量は、ループ版と同様に以下のようになります。

• 平均計算量・最悪計算量： O(n²)
• 最良計算量： O(n)（すでにソート済みの場合）
• 空間計算量： O(n)（再帰呼び出しによるスタック領域が必要）

なお、再帰版はループ版に比べてメソッド呼び出しのオーバーヘッドやスタック領域の消費があるため、大規模なデータには不向きです。あくまでアルゴリズムや再帰処理の学習用として理解しておくとよいでしょう。