アルゴリズムとデータ構造

クイックソートとは？

意味

ピボット（基準値）を選び、それより小さい要素と大きい要素に分割する操作を再帰的に繰り返す。平均計算量はO(n log n)と高速だが、最悪ケースはO(n²)になる。バブルソートや選択ソートより実用上はるかに速い。

?基本情報技術者試験での問われ方

基準値で大小に分割を繰り返す、平均O(n log n)の高速な整列アルゴリズムは何か？

答え：クイックソート

「クイック（速い）」＋「ソート」＝素早く仕分け。宅配便の仕分け作業で「大きい荷物」「小さい荷物」に次々分けるイメージ。