クイックソートとは
クイックソート（Quick Sort）とは、実用上で極めて高速に動作する代表的なソートアルゴリズムです。「分割統治法」と呼ばれる考え方に基づいており、まずデータの中から基準値（ピボット）を1つ決めます。次に、基準値より「小さい値のグループ」と「大きい値のグループ」の2つにデータを分けます。分けたそれぞれのグループに対して、再び同じルールでピボットを決めて二分する操作を再帰的に繰り返します。
具体例
学校でクラス全員を背の順に並べる際、適当な人（ピボット）を1人選び、「その人より背が低い人は左側、高い人は右側」に移動させます。その後、分けられた左右のグループそれぞれで再度同じリーダー（ピボット）を選んで整列を行う方法です。
// クイックソートの分割イメージ
[5, 2, 8, 9, 1, 3] (基準値を「5」とする)
│ (5より小さいグループと大きいグループに分ける)
▼
[2, 1, 3] ＜ 5 ＜ [8, 9]
※それぞれのグループで再度ソートを繰り返す。もう少し詳しく
クイックソート（Quick Sort）は、一般的に実用上最も高速とされる整列アルゴリズムです。「分割統治法（Divide and Conquer）」という、大きな問題を小さな問題に分割して解くアプローチを採用しています。処理の流れは以下の通りです。まず配列の中から「ピボット（基準値）」と呼ばれる要素を適当に1つ選びます。次に、ピボットより小さい要素を左側に、大きい要素を右側に集めるように配列を再配置します（パーティション分割）。これにより、ピボットの位置が最終的な整列位置として確定します。最後に、ピボットの左側（小さいグループ）と右側（大きいグループ）に対して、それぞれ再帰的にクイックソートを適用します。通常、配列の分割がバランス良く行われれば、時間計算量は O(N log N) となり、これは比較ベースのソートアルゴリズムの理論的限界値に近い極めて高速な性能です。しかし、ピボットの選び方が極端に悪く（例えば、すでに整列された配列に対して常に最小値や最大値をピボットに選んでしまうなど）、分割が片方に偏り続けると、最悪の場合の計算量は O(N^2) に劣化してしまいます。また、同値のデータの順序が崩れる「不安定ソート」です。
試験でのポイント
試験では、クイックソートの平均時間計算量が O(N log N) であり、最悪時間計算量が O(N^2) になる理由（ピボットの選び方による偏り）について問われます。ピボットの選定を最適化するために「配列の先頭・中央・末尾の3値の中央値を選ぶ」といった工夫（三値中値法）がなされる点も知識として重要です。また、再帰呼び出しを多用するため、プログラム上のコールスタックを多く消費し、最悪の場合にスタックオーバーフローを引き起こす可能性があるといった実装上の課題も問われることがあります。
関連する用語
分割統治法（問題を小さく切り分けてそれぞれ解決するアルゴリズム設計手法）、ピボット（クイックソートで要素を二分する際の基準値）、再帰（関数の中で自分自身を再び呼び出す処理）。