Pythonで挿入ソート（Insertion Sort）を実装する方法：アルゴリズムとサンプルコードを徹底解説

この記事では、Python 3.x（およびそれ以前のバージョン）における挿入ソートの実装方法について詳しく解説します。挿入ソートは、トランプの手札を整理するイメージに近い、直感的で理解しやすいソートアルゴリズムです。

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

挿入ソートは以下の手順で動作します。

• 入力要素を順番に走査し、各反復ごとにソート済みの配列部分を少しずつ拡張していきます。
• 現在注目している要素（キー）を、ソート済み部分の中で最も大きい値と比較します。
• キーがその値より大きければ、要素は元の位置のまま次の要素へ進みます。そうでなければ、ソート済み配列内の正しい位置を探し出し、そこへ移動させます。
• 具体的には、ソート済み配列内でキーより大きいすべての要素を一つずつ右側へシフトすることで、正しい位置を作り出します。

この流れを図で表すと、以下のようになります。

それでは、実際の実装を見ていきましょう。

実装例

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # keyより大きいarr[0..i-1]の要素を
        # 現在位置より一つ後ろへ移動させる
        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("ソート後の配列:")
for i in range(len(arr)):
    print(arr[i])

実行結果

ソート後の配列:
a
i
l
o
r
t
t
u

文字列のリストも問題なくアルファベット順にソートできていることがわかります。

計算量

時間計算量： O(n²) — 最悪の場合（逆順のデータ）、すべての要素について比較とシフトが発生します。一方、ほぼソート済みのデータに対しては高速に動作し、最良ケースではO(n)になります。

補助記憶域（空間計算量）： O(1) — ソートは元の配列内で完結するインプレース処理のため、追加のメモリはほとんど不要です。

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

まとめ

この記事では、挿入ソートの基本的な仕組みと、Python 3.x（およびそれ以前のバージョン）での実装方法を学びました。挿入ソートは小規模なデータセットやほぼ整列済みのデータに対して有効なアルゴリズムであり、クイックソートなどの高度なソートの一部としても利用されることがあります。ぜひ自分のコードでも試してみてください。