概要

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

アルゴリズム

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

$i\gets 1$
$j \gets 0$
ループ：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$
$i \gets i+1$
$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)$

実装

	import numpy as np

	class InsertionSort:
	def sort(self, array):
	a = array.copy()
	n = len(a)
	for i in range(1, n):
	for j in range(0, i):
	if a[i] <= a[j]:
	tmp = a[i]
	a[j+1:i+1] = a[j:i]
	a[j] = tmp
	return a

view raw ~6_insertion-sort.py hosted with ❤ by GitHub

テスト：

>>> 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