挿入ソート

挿入ソート#

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

計算量

最悪時間計算量

\(O(n^2)\)（逆順入力）

平均時間計算量

\(O(n^2)\)

最良時間計算量

\(O(n)\)（ほぼソート済み）

空間計算量

\(O(1)\)（in-place）

特徴

  • 安定ソート

  • in-place

  • ほぼソート済みのデータに非常に効率的

  • 小さい配列（\(n \lesssim 20\)）では定数係数が小さく実用的に速い（Timsort などの内部で使用）

アルゴリズム#

  1. インデックス i = 1 から開始し、arr[i] を key として取り出す

  2. ソート済み部分 arr[0:i] で key より大きい要素を1つ右にシフトする

  3. 空いた位置に key を挿入する

  4. 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]
Contents