挿入ソートとは？シンプルで効果的なソートアルゴリズムを図解で解説

アルゴリズム

2024.06.29

挿入ソートとは
1. アルゴリズムの概要
性能
1. 時間計算量
2. 空間計算量
特徴
実装(Python)
参考文献

挿入ソートとは

挿入ソートとは、

数列を昇順に並び替えるアルゴリズムの1つ

です。

挿入ソートは、トランプの手札を並び替えるときに使うような直感的でシンプルなソートアルゴリズムです。

新しいカードを受け取るたびに、既に持っているカードの適切な位置に挿入していくイメージです。

アルゴリズムの概要

左側にソート済みの部分を作成し、各要素をソート済みの適切な位置に挿入していきます。

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

- ステップ1
  
  先頭の要素をソート済みとする
- ステップ2
  
  未ソートの先頭をソート済みの適切な位置に挿入する
- ステップ3
  
  未ソートの部分がなくなるまでステップ2を繰り返す

性能

時間計算量

時間計算量は以下の通りです。

時間計算量

平均時間計算量: \(O(N^2)\)
最良の場合（ほぼソート済み）: \(O(N)\)
最悪の場合（逆順）: \(O(N^2)\)

空間計算量

空間計算量は、 \(O(1)\)（インプレース実装可能）

特徴

長所

実装が簡単
小さなデータセットに効果的(オーバヘッドが少ないため)
安定ソート（同じ値の要素の相対的な順序が保たれる）
ほぼソート済みのデータに対して非常に効率的

短所

大きなデータセットに対しては非効率(O(n^2)のため)

用途

小規模のデータのソート
ほぼソートされたデータの整理
他のアルゴリズムのサブルーチン
(マージソートやクイックソートのようなオーバーヘッドの大きい分割統治ソートアルゴリズムの再帰的な基本ケースとして使う)

実装(Python)

def insertion_sort(nums):
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            if nums[j - 1] < nums[j]:
                break
            nums[j], nums[j - 1] = nums[j - 1], nums[j]


nums = [4, 2, 3, 1]
insertion_sort(nums)
print(nums)