2 単純挿入ソート

原理については，教科書に分かりやすくかかれているので，それを使って説明する．説明するまでもなく，教科書を一読すれば，直ちに原理は理解できるであろう．

計算量のオーダーについて，簡単に説明する．左から$i$ 個，整列が完了して，$i+1$ 個目を整列させることを考える．

• 数列の$i+1$ 番目が挿入されるべき位置を見つけるための比較の平均回数(期待値)は，$i/2$ である．
• 位置が見つかった場合，それを挿入するために，配列は平均で$i/2$ の交換が必要である．

このことから，数列の$i+1$ 番目を正しい位置に挿入するためには，合わせて$i$ 回の計算²が必要となる．大きさが$N$ の数列全体では，

$$\sum_{i=1}^{N-1}i =\frac{(N-1)(N-2)}{2}$$

$$=\frac{1}{2}N^2-\frac{3}{2}N+1$$ (1)

となる．$N$ が大きい場合，$N^2/2$ が支配的で$N^2$ に比例して，計算量が増加する．このような場合，計算量のオーダーを表す記号として$O(N^2)$ と書くのは，以前述べたとおりである．

2.1 単純挿入ソートの様子

教科書のプログラム(List 1-7)を使った場合の単純挿入ソートの様子を図1に示す．ただし，教科書とは異なり，数列(配列)の大きさは$N=20$ としている．

図 1: 単純挿入ソートの様子．

ホームページ: Yamamoto's laboratory
著者: 山本昌志