Pythonで実装する再帰的挿入ソートのプログラム

はじめに

この記事では、再帰的な手法を用いた挿入ソートをPythonで実装する方法について解説します。

問題文

問題： 配列が与えられたとき、再帰的挿入ソートの考え方を使って昇順に並べ替えてください。

挿入ソートは、整列済みの部分配列を作りながら、そこへ要素を適切な位置に一つずつ挿入していくアルゴリズムです。通常はfor文などのループで実装されますが、今回は再帰呼び出しを利用して実装します。

アルゴリズムの流れ

1. 先頭から n-1 個の要素を再帰的にソートする
2. n 番目の要素（last）を取り出す
3. last より大きい要素を後ろへ一つずつずらし、正しい位置に last を挿入する

サンプルコード

# 再帰による実装
def insertionSortRecursive(arr,n):
    # ベースケース
    if n<=1:
        return
    # n-1 個の要素を再帰的にソート
    insertionSortRecursive(arr,n-1)
    last = arr[n-1]
    j = n-2
    # 大きい要素を後ろへずらす
    while (j>=0 and arr[j]>last):
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1]=last
# メイン処理
arr = [1,5,3,4,8,6,3,4,5]
n = len(arr)
insertionSortRecursive(arr, n)
print("Sorted array is:")
for i in range(n):
    print(arr[i],end=" ")

実行結果

Sorted array is :
1 3 3 4 4 5 5 6 8

処理のポイント

すべての変数はローカルスコープ内で宣言されており、再帰呼び出しごとに独立した値が扱われます。ベースケース（n <= 1）に到達すると再帰が終了し、呼び出し元へ戻る過程で要素が順番に正しい位置へ挿入されていきます。

計算量については、最悪・平均ともに O(n²) となります。また、再帰呼び出しの分だけスタック領域が必要になるため、空間計算量は O(n) です。小規模なデータやほぼ整列済みのデータに対しては効率よく動作します。

まとめ

この記事では、Pythonで再帰的挿入ソートを実装する方法を学びました。ループ版との違いや再帰構造の理解を深める良い練習例なので、ぜひ自分でもコードを書いて動作を確認してみてください。