基本情報技術者 予想問題｜A 第15問

解説

クイックソートは、基準値（ピボット）を選び、それより小さい要素のグループと大きい要素のグループに分割する操作を再帰的に繰り返す分割統治法のソートであり、平均計算量はO(n log n)である。よってイが正解である。アについて、最悪計算量はO(n)ではなくO(n^2)であり、整列済みデータで端の要素をピボットに選び続けるなど、分割が極端に偏った場合に発生する。ウについて、クイックソートは等しい値の要素の元の順序が保たれない不安定ソートである。エについて、再帰呼出しのためのスタック領域などの作業メモリを必要とする。基本情報技術者試験では、各ソート（バブル・選択・挿入・クイック・マージ・ヒープ）の平均・最悪計算量と安定性の比較が頻出ポイントであり、クイックソートの「平均は高速だが最悪はO(n^2)」という特徴は確実に押さえたい。