ALDS1_6_C:

クイックソートは次のような分割統治法に基づくアルゴリズムです。

クイックソート
- 配列全体を対象として quick_sort を実行する。
- quick_sort は次の通り：
1. partition により、対象の部分配列を前後２つの部分配列へ分割する。（Divide）
2. 前方の部分配列に対して quick_sort を行う。（Solve）
3. 後方の部分配列に対して quick_sort を行う。（Solve）

クイックソートの関数 quick_sort は次の図のように、部分配列を partition により２つに分割し、２つのグループそれぞれに再帰的に quick_sortを行うことで与えられた配列を

整列します。たとえば、$A = \{13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 5, 3, 14, 6, 11\}$ に対してクイックソートを行うと次のようになります。

クイックソート

クイックソートはマージソートと同様に分割統治法に基づくアルゴリズムですが、分割してパーティションを行ったときに既に元の配列内でソートが完了するので、（マージソートのように）統治にあたる明示的な処理がありません。

クイックソートは、partition の内部で離れた要素を交換するので、安定なソートアルゴリズムではありません。一方で、マージソートが $O(N)$ の外部メモリを必要としたのに対し、クイックソートは追加のメモリ領域を必要としない、いわゆるインプレースソート（内部ソート）であるという特長があります。

クイックソートは partition においてバランスよく半分ずつ分割されていけば、マージソートと同様におおよそ $\log_2 N$ 段の階層ができます。クイックソートの平均計算量は $O(N \log N)$ で、一般的に最も高速なソートアルゴリズムとして知られています。しかし、問題の疑似コードで示されたクイックソートは、基準の選び方が一定なので、データの並びによっては（たとえば既にソートされているデータ）に対して効率が悪くなり、最悪の場合 $O(N^2)$ の計算量になってしまいます。データの並びによっては再帰が深くなりスタックオーバーフローが起こる可能性もあります。通常は、基準をランダムに選ぶ、配列から適当な値を選びその中央値を選ぶ、などして基準の選び方を工夫する必要があります。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。