スマートフォン用の表示で見る

クイックソート

【quicksort】整列アルゴリズムのひとつ。対象を昇順、降順に並べ替える代表的方法。

アルゴリズム

クイックソートの手続きは以下のとおり:

  1. 中間的な基準値を決める
  2. 要素を移動し、基準値より大きな値の要素を集めた部分と小さな値の要素を集めた部分とに分割する。
  3. 次にそれぞれの部分の中で同様な処理を繰り返す

クイックソートの本質は再起にある。上の手続きのうち、3番目の作業、実は作り上げたそれぞれの部分に対して再起処理を行うことを示している。したがって、上の手続きは以下のように書き換えることができる。

  1. 中間的な基準値を決める
  2. 要素を移動し、基準値より大きな値の要素を集めた部分と小さな値の要素を集めた部分とに分割する。
  3. それぞれの部分にクイックソートを施す

歴史

クイックソート英国コンピュータ学者、C.A.R.Hoarによって考案された。彼はFOTRANで苦心してクイックソートを実装し、上司との「シェルソートより早いか」という賭けに勝った。このとき、FORTRAN実装で苦心した経験が、当時提案されていたAlgol支持へと彼を向かわせた。

計算量と性質

クイックソートの計算時間は基準値の選び方に強く依存する。理想的な場合、クイックソートの計算量はO(N)=N*log(N)であることが知られている。これはヒープソートと同等であり、ソートアルゴリズムとしては最速の部類である。

基準値の選び方をしくじると、クイックソートは最悪N^2の計算量を必要とすることがある。また、そのようなケースではスタックの消費も著しいものになる。そのため、実用的な実装ではオーバーヘッドを覚悟の上で基準値の選び方に工夫を凝らしてある。

また、二つの要素の評価値が等しい場合、クイックソートはその2要素の並びを保存しない(「安定なソート」でない)。この性質を嫌うアプリケーションでは、クイックソートを使えない。