挿入ソート単語

2件

ソウニュウソート

1.4千文字の記事

掲示板へ

記事編集

挿入ソートはソートアルゴリズムの一種である。

平均計算時間はO(n^2)で、普段はバブルソートよりマシ程度の性能だが、特定の条件下では途端にデキる子になる。バブルソートとは違うんです。安定ソート。

原理

ソート済みの配列がある時、新たな値が入る場所は一箇所に決まるので、適切な場所に値を挿入し以降の値をずらすことでソート済みという性質を保ったまま配列を伸ばせる。

この要領で配列の先頭にソート済み部分を蓄積し、直後の値をソート済み部分のどこかに差し込む手順を繰り返すことで全体を並び替えることができる。

ちなみに比較順序は前後どちらからスタートしても原理的には動くが、普通は後ろから行う。こうすることで安定ソートにできるのと、後述するベストケースの利点を活かせるからである。

性能検討

値を一つ加えるごとにソート済みの値全てを候補とした比較が入りうるから、単純に計算すると比較回数は1+2+...+n-1=n(n-1)/2、というところまではバブルソートと同じ。実際は挿入場所が決まれば以降を省略できるので、平均すると比較はバブルソートの半分ぐらいで済むことになる。同じO(n^2)でもバブルソートより速いのはこのため。

値の交換に関しては、挿入位置の後ろをまるっとずらす必要があるので、普通の配列上だとバブルソートと同レベル。ただし、挿入を定数時間でできる連結リストの場合、必要なのはソート全体を通して最大で長さ-1回となり、扱うデータ構造によって効率が変わってくるという特徴がある。

とはいえ、平均してO(n^2)という事実は動かしがたいため、対象の長さや状態を読めない時の汎用ソートとしてはまず使わないだろう。

適材適所

このようにパッと見る限りさほど素性のよくなさそうな挿入ソートだが、実はうまく使うと他の高速ソートより優れた性能をだすことがある。

ほぼソート済みの配列に対しては速い
配列がソート済みの時、次の値はソート済み部分末尾の直後とすぐ分かるから、一ループ毎に比較1回+交換なしと速い。原理のところで触れた、比較順序を後ろからにするメリットはこれである。
交換が生じた場合も、その値の移動に手間が掛かる以外は、以降末尾の値が入れ替わった数だけ比較、交換が増えうるのみで済む。バブルソートのように並びが悪いと極端に遅くなるようなこともないので、常にソート済みが前提の配列で時々2,3個順位が入れ替わるといったような用途には向いている。
実装が非常にシンプル
原理が単純なので実装が非常にシンプルである。プログラマが楽できるだけと思うかもしれないが、コードがシンプルということは一ループ辺りの実行時間が短いということであり、特に要素数が少ない時このインパクトは無視できないものがある。CPU キャッシュ的にも実装が小さいことは利点。理論上の計算オーダーが悪くても実装のコンパクトさで性能が勝るということはあるのだ。
連結リストに強い
上述の通り、挿入が定数時間のデータ構造ではそのメリットを最大限に活かせる。