概要

配列のソートアルゴリズムの1つ。

アルゴリズム

ソート対象配列の長さ $n$ の配列について、$i$ 番目の要素を $a_i$ で表す（$i=0,1,2,\cdots,n-1$）。

  1. $i\gets 1$
  2. $j \gets 0$
  3. ループ：$j = i$ となるまで以下の操作を繰り返す
    1. $a_i \le a_j$ であれば $j$ 番目の位置に $a_i$ を挿入し、$a_j,a_{j+1},\cdots,a_{i-1}$ を一つずつ後ろにシフトしてループを抜ける
    2. $j \gets j+1$
  4. $i \gets i+1$
  5. $i \le n$ なら2へ戻る。$i\gt n$ ならソート終了

具体例

[ 4   1   5   3   2 ]
 <->  ^i=1
 sorted

先頭から i 番目までの（ソート済み）部分配列の要素を順番に見ていく。
初めて見つかる a_i=1 以上の値は a_0=4 なので、a_0 の手前に a_i を挿入して i をインクリメント: i <- i+1

[ 1   4   5   3   2 ]
 <----->  ^i=2
 sorted

先頭から i 番目までの（ソート済み）部分配列の要素を順番に見ていく。
a_i=5 以上の値は見つからないので挿入は行わずに i をインクリメント: i <- i+1

[ 1   4   5   3   2 ]
 <--------->  ^i=3
 sorted

先頭から i 番目までの（ソート済み）部分配列の要素を順番に見ていく。
初めて見つかる a_i=3 以上の値は a_1=4 なので、a_1 の手前に a_i を挿入して i をインクリメント: i <- i+1

[ 1   3   4   5   2 ]
 <------------->  ^i=4
 sorted

先頭から i 番目までの（ソート済み）部分配列の要素を順番に見ていく。
初めて見つかる a_i=2 以上の値は a_1=3 なので、a_1 の手前に a_i を挿入して i をインクリメント: i <- i+1

[ 1   2   3   4   5 ]
 <----------------->  ^i=5
 sorted

--> ソート完了

計算量

時間計算量

挿入する要素 $a_i$ それぞれについて、$a_0, a_1, \cdots, a_{i-1}$ を走査する必要があり、各ループで走査が必要な要素の数は以下の通り。

  • $i=1$：$a_0$ を走査
  • $i=2$：$a_0,a_1$ を走査
  • $i=3$：$a_0,a_1,a_2$ を走査
  • $\cdots$
  • $i=n$：$a_0, a_1, \cdots, a_{n-1}$ を走査

走査すべき要素の総数は $n(n+1)/2$ なので、時間計算量は $O(n^2)$

【NOTE】

$a_0, a_1, \cdots, a_{i-1}$ をすべて走査せずとも、途中で $a_i \le a_j$ となる $j$ が見つかれば、それ以降の要素を捜査する必要はなくなる。
しかし、結局はその後 $a_i$ を $a_j$ の前に挿入するために玉突きのように $a_j, a_{j+1}, \cdots, a_{i-1}$ を1つずつ後ろに動かす作業が必要になるので、やはり計算回数は変わらない。

空間計算量

元の配列自体の要素を入れ替える方式なので、追加のメモリを必要としない。
したがって空間計算量は $O(n)$

実装

テスト：

>>> test_sort_algorithm(InsertionSort())
OK: [1, 6, 2, 7, 5, 4, 3] --> [1 2 3 4 5 6 7]
OK: [2, 4, 3, 7, 6, 5, 1] --> [1 2 3 4 5 6 7]
OK: [3, 1, 5, 7, 6, 4, 2] --> [1 2 3 4 5 6 7]
OK: [3, 6, 5, 7, 4, 2, 1] --> [1 2 3 4 5 6 7]
OK: [4, 3, 7, 6, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [5, 2, 1, 7, 6, 4, 3] --> [1 2 3 4 5 6 7]
OK: [5, 7, 2, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [6, 4, 3, 7, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [7, 2, 5, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [7, 6, 5, 4, 3, 2, 1] --> [1 2 3 4 5 6 7]
All 5040 tests passed.

（参考）test_sort_algorithm：指定した長さの全ての組み合わせの配列を生成してソート結果をテストする関数

平均時間計算量 $O(n^2)$ の確認：

Ns = np.arange(1, 10+1) * 1000
ave, std = experiment_computing_time(InsertionSort(), Ns)
draw_computing_order(Ns, ave, std)

insertion-sort