挿入ソート - データサイエンス関連+αのメモ

挿入ソート（insertion sort） は未ソートの要素を1つずつ取り出し、ソート済み部分の適切な位置に挿入するアルゴリズム。トランプの手札を並べるイメージ。

	計算量
最悪時間計算量	$O(n^2)$ （逆順入力）
平均時間計算量	$O(n^2)$
最良時間計算量	$O(n)$ （ほぼソート済み）
空間計算量	$O(1)$ （in-place）

特徴

安定ソート
in-place
ほぼソート済みのデータに非常に効率的
小さい配列（ $n \lesssim 20$ ）では定数係数が小さく実用的に速い（Timsort などの内部で使用）

アルゴリズム¶

インデックス i = 1 から開始し、arr[i] を key として取り出す
ソート済み部分 arr[0:i] で key より大きい要素を1つ右にシフトする
空いた位置に key を挿入する
i を進めて繰り返す

def insertion_sort(arr: list) -> list:
    a = arr.copy()
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

import random

data = [12, 11, 13, 5, 6]
print("入力:", data)
print("出力:", insertion_sort(data))

# ほぼソート済みデータで高速動作を確認
nearly_sorted = list(range(100))
nearly_sorted[50], nearly_sorted[51] = nearly_sorted[51], nearly_sorted[50]
assert insertion_sort(nearly_sorted) == list(range(100))
print("ほぼソート済み100件: OK")

random.seed(1)
large = random.sample(range(1000), 20)
assert insertion_sort(large) == sorted(large)
print("ランダム20件: OK")

入力: [12, 11, 13, 5, 6]
出力: [5, 6, 11, 12, 13]
ほぼソート済み100件: OK
ランダム20件: OK

ステップ可視化¶

def insertion_sort_verbose(arr: list) -> list:
    a = arr.copy()
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
        print(f"i={i}, key={key}: {a}")
    return a

data = [5, 3, 8, 1, 4]
print("入力:", data)
insertion_sort_verbose(data)

入力: [5, 3, 8, 1, 4]
i=1, key=3: [3, 5, 8, 1, 4]
i=2, key=8: [3, 5, 8, 1, 4]
i=3, key=1: [1, 3, 5, 8, 4]
i=4, key=4: [1, 3, 4, 5, 8]

[1, 3, 4, 5, 8]

二分探索による改良¶

挿入位置を線形探索ではなく二分探索で求めることで比較回数を $O(n \log n)$ に削減できる。ただしシフト操作は $O(n^2)$ のままなので、時間計算量全体は変わらない。

from bisect import bisect_left

def binary_insertion_sort(arr: list) -> list:
    a = arr.copy()
    for i in range(1, len(a)):
        key = a[i]
        pos = bisect_left(a, key, 0, i)  # 挿入位置を二分探索
        a[pos + 1:i + 1] = a[pos:i]      # シフト
        a[pos] = key
    return a

data = [5, 3, 8, 1, 4]
print(binary_insertion_sort(data))
assert binary_insertion_sort(data) == sorted(data)

[1, 3, 4, 5, 8]