Pythonで学ぶ挿入ソート（Insertion Sort）の仕組みと実装方法

この記事では、Python 3.xにおける挿入ソート（Insertion Sort）の基本的な考え方と、実際のコードによる実装方法をわかりやすく解説します。

挿入ソートのアルゴリズム

挿入ソートは、配列を「整列済みの部分」と「未整列の部分」に分け、未整列の要素を一つずつ取り出して、整列済み部分の正しい位置に挿入していくシンプルなソート手法です。処理の手順は以下の通りです。

1. 各反復ごとに整列済みの配列を少しずつ拡大しながら、入力要素を走査する。
2. 現在の要素（キー）を、整列済み配列内の最大値と比較する。
3. キーがその最大値より大きければ、要素はそのままの位置に置かれ、
   次の要素へ進む。そうでなければ、整列済み配列の中からキーの
   正しい位置を見つけ出し、そこへ移動させる。
4. この移動は、整列済み配列内でキーより大きいすべての要素を
   一つ後ろの位置へずらすことで実現される。

次に、このアルゴリズムの動作イメージを図で確認してみましょう。

それでは、具体的な実装を見ていきましょう。

実装例

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # arr[0..i-1] のうち key より大きい要素を、
        # 現在位置より一つ後ろへ移動させる
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
# メイン処理
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
    print (arr[i])

実行結果

The sorted array is:
a
i
l
o
r
t
t
u

文字列のリストも問題なくアルファベット順に並び替えられていることが確認できます。

計算量について

• 時間計算量： O(n²) — 最悪の場合、すべての要素同士を比較するため二乗オーダーとなります。
• 補助記憶領域（空間計算量）： O(1) — 追加のメモリをほとんど必要としないため、インプレース（in-place）なソートです。

下図のように、すべての変数はグローバルフレーム上で宣言・管理されています。

まとめ

この記事では、挿入ソートの基本的なアルゴリズムと、Python 3.xでの実装方法を紹介しました。挿入ソートはコードがシンプルで理解しやすく、すでにほぼ整列されたデータに対しては高速に動作するという特徴があります。小規模なデータセットや学習用途には最適なアルゴリズムなので、ぜひ自分でもコードを書いて動作を確かめてみてください。