Javaで学ぶ再帰的挿入ソートの実装方法とコード解説

挿入ソートは、配列の要素を1つずつ取り出し、すでにソート済みの部分に適切な位置へ挿入していくシンプルな整列アルゴリズムです。本記事では、この挿入ソートを再帰（リカーシブ）を用いて実装するJavaプログラムを紹介します。

再帰的挿入ソートのサンプルコード

以下は、再帰呼び出しによって挿入ソートを実現するJavaプログラムの例です。

import java.util.Arrays;
public class Demo{
    static void recursive_ins_sort(int my_arr[], int arr_len){
        if (arr_len <= 1)
            return;
        recursive_ins_sort( my_arr, arr_len-1 );
        int last = my_arr[arr_len-1];
        int j = arr_len-2;
        while (j >= 0 && my_arr[j] > last){
            my_arr[j+1] = my_arr[j];
            j--;
        }
        my_arr[j+1] = last;
    }
    public static void main(String[] args){
        int my_arr[] = {11, 23, 67, 83, 42, 11, 0};
        recursive_ins_sort(my_arr, my_arr.length);
        System.out.println("挿入ソート実行後の配列要素は次の通りです：");
        System.out.println(Arrays.toString(my_arr));
    }
}

実行結果

挿入ソート実行後の配列要素は次の通りです：
[0, 11, 11, 23, 42, 67, 83]

プログラムの仕組み

まず、Demoという名前のクラス内に、挿入ソートを行う静的な再帰関数 recursive_ins_sort を定義しています。この関数は、対象となる配列とその長さを引数として受け取ります。

処理の流れは以下の通りです。

• 基底条件： 配列の長さが1以下の場合、それ以上ソートする必要がないため、そのまま処理を終了します。
• 再帰呼び出し： それ以外の場合は、配列のサイズを1つずつ減らしながら自分自身を再帰的に呼び出し、先頭側から順に部分配列をソートしていきます。
• 要素の挿入： 部分配列がソートされた後、末尾の要素（キー）を取り出し、その正しい位置を探索します。キーより大きい要素が見つかれば、その要素を一つ後ろの位置へずらし、適切な位置にキーを挿入します。

このようにして、各要素が順番に正しい位置へ配置され、最終的に配列全体が昇順にソートされます。処理が完了すると、結果がコンソールに出力されます。

計算量について

再帰的挿入ソートの計算量は、反復版と同様に最悪・平均ケースで O(n²) となります。一方、配列がほぼソート済みの場合は O(n) で動作します。また、再帰呼び出しを使用するため、深さ n のスタック領域が必要となり、空間計算量は O(n) です。大きなデータセットには不向きですが、小規模な配列や学習目的には非常に有用なアルゴリズムです。