IT用語入門：クイックソート【分割統治で高速に並べ替える】

クイックソートとは

クイックソートとは、配列などのデータを並べ替えるアルゴリズムの一つです。1960年にイギリスの計算機科学者アントニー・ホーアが考案しました。一般にとても高速ですが、データの並びによっては最速にならないこともあります。

仕組みは、データから基準値（ピボット）を一つ選び、基準より小さいものと大きいものに分けることです。分けたそれぞれに同じ操作を繰り返し、グループが要素一つになるまで進めます。大きな問題を分けて処理しやすくする分割統治法の代表例です。

速さは基準値の選び方に左右されます。中央値が理想ですが、見つけるコストが高いため、先頭要素を使ったりランダムに選んだりする方法がよく使われます。実装が比較的簡単で大型データにも強い一方、入力の偏り次第で性能が落ちるため、状況に応じた使い分けが大切です。