クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。n個のデータをソートする際の最良計算量および平均計算量はOformula_1である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOformula_2である。また数々の変種がある。安定ソートではない。実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。ピボットは、通常、データ列からランダムに選んだり、データ列中の適当な三つ程度の数の中央値を選ぶ。このように、ピボットの選び方を工夫することで、最悪計算時間がかかってしまうような入力データ列の可能性を抑える。他にも、ピボットを選ぶ前に入力データ列をランダムに並び替える、などの手法を上記の工夫と合わせて使うことで、入力データ列のソートに最悪計算時間を必要とする可能性を抑えることができる。また、再帰的にソートする際、対象となるデータの数が少なくなったら、挿入ソートなどの別のアルゴリズムを適用することで高速化する手法が研究されている。確定した部分は太文字で表す。ピボットには下線を引く。初期データ: 8 4 3 7 6 5 2 1C言語によるクイックソートの実装例を示す。typedef int value_type; /* ソートするキーの型 *//* x, y, z の中間値を返す */value_type med3(value_type x, value_type y, value_type z) {/* クイックソートvoid quicksort(value_type a[], int left, int right) {

出典:wikipedia