【quicksort】整列アルゴリズムのひとつ。対象を昇順、降順に並べ替える代表的方法。
クイックソートの手続きは以下のとおり:
クイックソートの本質は再起にある。上の手続きのうち、3番目の作業、実は作り上げたそれぞれの部分に対して再起処理を行うことを示している。したがって、上の手続きは以下のように書き換えることができる。
クイックソートは英国のコンピュータ学者、C.A.R.Hoarによって考案された。彼はFOTRANで苦心してクイックソートを実装し、上司との「シェルソートより早いか」という賭けに勝った。このとき、FORTRAN実装で苦心した経験が、当時提案されていたAlgol支持へと彼を向かわせた。
クイックソートの計算時間は基準値の選び方に強く依存する。理想的な場合、クイックソートの計算量はO(N)=N*log(N)であることが知られている。これはヒープソートと同等であり、ソートアルゴリズムとしては最速の部類である。
基準値の選び方をしくじると、クイックソートは最悪N^2の計算量を必要とすることがある。また、そのようなケースではスタックの消費も著しいものになる。そのため、実用的な実装ではオーバーヘッドを覚悟の上で基準値の選び方に工夫を凝らしてある。
また、二つの要素の評価値が等しい場合、クイックソートはその2要素の並びを保存しない(「安定なソート」でない)。この性質を嫌うアプリケーションでは、クイックソートを使えない。