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

4.4

 分割ベースのソート

■

79

4.4.3

 分析

驚くべきことだが、ピボット選択にランダムアルゴリズムを使った

クイックソート

は他の整列アルゴリズムよりも優れた平均時性能を示す。さらに、

クイックソート

には、数多くの修正や最適化が研究されており、どの整列アルゴリズムよりも性能

について研究されてきた。

理想的な場合、

partition

が元の配列を半分に分けて

O(n log n)

性能を示す。実

用上、

クイックソート

は、

pivot

がランダムに選ばれた場合に威力を発揮する。

最悪時は、ピボットとして最大値か最小値が選ばれた場合で、

クイックソート

は、

配列の

1

要素を整列するために全要素を（線形時間で）調べなくてはいけない。この

過程が

n

−

1

回繰り返されるので、結果的に、最悪時

O(n

2

)

の振る舞いとなる。

4.4.4

 変形

ほとんどのシステムで、整列に

クイックソート

が用意されている。

Unix

ベースの

システムには、

qsort

という組み込みのライブラリ関数がある。オペレーティング

システムでは、通常の

クイックソート

アルゴリズムの最適化版を使用することが多

い。よく参照される最適化には、

Sedgewick

（

1978

）と

Bentley and McIlroy

（

1993

）

の

2

つがある。

Linux

のバージョンによっては、

ヒープソート

を使って

qsort

を実装

しているのは教訓的だ。

最適化には次のようなものがある。

●

再帰処理を省くため、部分タスクを貯えるためのスタックを作る。

●

「

3

個の中央値」（

median-of-thre ...