3 2分挿入ソート

3.1 原理

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

計算量のオーダーに関しては，教科書の説明は不十分である．先ほどと同様に，左から$i$ 個，整列が完了して，$i+1$ 個目を整列させることを考える．

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

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

$$\sum_{i=1}^{N-1}\left(\frac{i}{2}+\log_2 i\right) =\frac{(N-1)(N-2)}{4}+\log_2(N-1)!$$

$$N n!\simeq\sqrt{2\pi n}n^n e^{-n}$$

$$\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2}+\log_2\left[ \sqrt{2\pi (n-1)}(n-1)^{(n-1)} e^{-n+1} \right]$$

$$\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2} +\frac{1}{2}\log_2\left[2\pi (n-1)\right] +(n-1)\log_2(n-1) +(1-n)\log_2 e$$ (2)

となる．$N$ が大きい場合，$N^2/4$ が支配的で$N^2$ に比例して，計算量が増加する．従って，計算量のオーダーは，$O(N^2)$ である．

これまでの計算から，2分挿入ソートは，単純挿入ソートに比べて，2倍程度の速度の増加であることが分かる．

3.2 2分挿入ソートの様子

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

図 2: 2分挿入ソートの様子．

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