Pythonの挿入ソートとは？仕組みと実装方法をわかりやすく解説

挿入ソート（Insertion Sort）は、配列を並べ替えるための最もシンプルなアルゴリズムのひとつです。この手法では、配列を仮想的に「ソート済みの部分」と「未ソートの部分」に分けます。そして、未ソート部分から要素をひとつ取り出し、ソート済み部分の中の正しい位置へ挿入していくことで、全体を昇順に並べ替えます。

挿入ソートの基本的な考え方

• 配列の要素を、インデックス1からn−1まで順番に走査します。
• 位置iの要素が直前の要素（位置i−1）より大きい場合、その要素は動かす必要がありません。
• 位置iの要素が直前の要素より小さい場合、自分より小さい要素が見つかるか、配列の左端（インデックス0）に到達するまで、要素を左方向へずらしていきます。

具体例で理解する

次の配列を例に、挿入ソートの流れを確認してみましょう。

走査はインデックス1から始めます。インデックス0には比較対象となる先行要素が存在しないためです。

インデックス1の場合

6は直前の要素（4）より大きいため、何もする必要がありません。

インデックス2の場合

1は直前の要素より小さいため、自分より小さい要素が見つかるか、インデックス0に到達するまで左へずらします。この例ではインデックス0まで移動し、配列は次のように並び替えられます。

インデックス3の場合

7は直前の要素（6）より大きいため、そのままの位置に留まります。

インデックス4の場合

2は直前の要素より小さいため、2より小さい要素（1）が見つかるまで左へずらします。

インデックス5の場合

5は直前の要素より小さいため、5より小さい要素（4）が見つかるまで左へずらします。

これで、ソート済みの配列が完成しました。

計算量について

挿入ソートはin-place（追加のメモリをほとんど必要としない）アルゴリズムであり、時間計算量はO(n²)、空間計算量はO(1)です。要素数が少ないデータや、ほぼ整列済みのデータに対しては非常に効率的に動作するという特徴があります。

Pythonでの実装例

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 各要素を取り出す
        j = i - 1
        # インデックス0に達するか、keyより小さい要素が見つかるまで左へずらし続ける
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [4, 6, 1, 7, 2, 5]
insertionSort(arr)
for i in range(len(arr)):
    print(arr[i], end=' ')

出力結果

1 2 4 5 6 7