クイックソート

一言で言うと

ピボットを基準に配列を分割しながら整列する、分割統治型のソートアルゴリズム。平均計算量は O(n log n)。

もう少し詳しく

配列からピボット（基準値）を1つ選び、それより小さい要素と大きい要素の2グループに分割します。この操作を各グループに対して再帰的に繰り返すことで、配列全体が整列されます。平均計算量は O(n log n) ですが、ピボット選択が偏ると最悪 O(n²) になる点も知っておくと実務で役立ちます。

計算量・効率性を意識した設計に必要な概念です。実務では既存ライブラリを使うことが多いですが、内部の仕組みを知っておくと適切な選定とデバッグができるようになります。

実務でどう使うか

関連する章

Ch94 で詳しく学べます。