テクノロジ系出題頻度 3/3
クイックソート
くいっくそーと
定義
基準値（ピボット）で分割し再帰的に整列する高速ソート法。平均O(n log n)。
詳細解説
1960年トニー・ホーア考案。ピボットを選び、それより小さい要素と大きい要素に分割（パーティション）し、各部分を再帰的にソートする分割統治アルゴリズム。平均O(n log n)で、定数項が小さく実用的に最速級。ただしピボット選択が悪いと最悪O(n²)（既ソート列に最初/最後要素をピボットとした場合）。ランダム化、メディアン・オブ・スリー等で回避する。その場ソートだが安定ではない。多くの標準ライブラリのソート関数の中核。
「クイックソート」が出る問題
関連用語
よくある質問
Q. クイックソートとは何ですか？
A. 基準値（ピボット）で分割し再帰的に整列する高速ソート法。平均O(n log n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。