アルゴリズムクイックリファレンス 第2版

4.1

 転置ソート

■

65

挿入ソート

は、余分なスペースをほとんど必要としない。要素

1

つ分のスペース

を確保するだけでよい。値による格納方式の場合、ほとんどのプログラミング言語

のライブラリで、メモリ転置を効率的に行うブロックメモリ移動関数が用意されて

いる。

4.1.4

 分析

挿入ソート

は、最良時、要素は整列されていて、線形時間

O(n)

になる。これは、

当たり前すぎること（既に整列されている要素を整列しようとすることは何回ある

だろうか）に思えるかもしれないが、

挿入ソート

だけがこの振る舞いを示す比較整列

アルゴリズムとなる。

多くの実世界のデータは、実は「部分整列」しているので、楽観主義者も現実主義

者も効率的なアルゴリズムとして

挿入ソート

を推すかもしれない。重複データがあ

ると整列時の要素入れ替え回数が減るので、

挿入ソート

の効率が向上する。

しかし、

挿入ソート

は残念ながら、

n

個の要素の値がすべて異なり、配列が「ラ

ンダム」

な（データのすべての順列が同じ程度に起こる）データに対して効率が

悪い。なぜなら、各要素は、本来の位置から平均して

n/3

離れたところにある

からだ。コードリポジトリのプログラム

numTranspositions

（

Code/Chapter4/

numTranspositions.c

）は、

12

までの小さな

n

について、このことを実験的に確認

している。（

Trivedi, 2001

）も参照すること。そこで

挿入ソート

は、平均時および

最悪時には、

n

個の要素それぞれが

n

の定数倍だけ位置を変更しなけ ...