ALDS1_6_C:

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

• 配列全体を対象として quickSort を実行する。
• quickSort は次の通り：
  partition により、対象の部分配列を前後２つの部分配列へ分割する。（Divide）
  前方の部分配列に対して quickSort を行う。（Solve）
  後方の部分配列に対して quickSort を行う。（Solve）
  

クイックソートの関数 quickSort は次の図のように、部分配列を partition により２つに分割し、２つのグループそれぞれに再帰的に quickSort を行うことで与えられた配列を整列します。例えば、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 のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。