Optimized C++ ―最適化、高速化のためのプログラミングテクニック

90

5 章　アルゴリズムを最適化する

という性能になる。最悪時を確実に避けることはできず、素朴な実装の性能はしばしば劣る。

•

挿入ソートを含めて一部のソートは、ランダムデータでは性能が良くないにもかかわらず、

データがほとんど整列している場合に優れた（線形）性能を示す。しかし他のソートは（先ほ

ど述べた素朴なクイックソートを含めて）整列済みデータで最悪時性能を示す。データが通常

整列済みかほとんど整列している場合に、このような追加特性に関する知識を整列済みデータ

に対し性能の優れたソートの選択に使うことができる。

5.4.1

　整列アルゴリズムの時間コスト

代表的な整列アルゴリズムの入力の最良時、平均時、最悪時の時間計算量を表

5-3

に示す。ほ

とんどのソートが同じ

O(n log

2

n)

平均時性能を示すが、最良時と最悪時の性能、および追加で必

要なスペース量が異なっている。■

表

5-3

 代表的な整列アルゴリズムの時間コスト

ソート 最良時 平均時 最悪時 必要スペース 最良 / 最悪時の注記

挿入ソート

n n

2

n

2

1

最良時は（ほとんど）整列済みデータ

クイックソート

n log

2

n n log

2

n n

2

log

2

n

最悪時は整列済みデータでピボットを素朴（先頭

/

末

尾）に選んだとき

マージソート

n log

2

n n log

2

n n log

2

n 1

ツリーソート

n log

2

n n log

2

n n log

2

n n

ヒープソート

n log

2

n n log

2

n n log

2

n 1

ティムソート ...