修了試験 2013-01-27実施分 基本情報技術者試験 問5

解説

正解は3です。 クイックソートは、基準値（ピボット）を選んでデータを2つのグループに分ける操作を繰り返す整列法です。 分割したグループに同じ処理を再帰的に適用します。 平均計算量はO(n log n)で、実用上とても高速な方法です。 【選択肢別解説】 1：× 整列済みの列の正しい位置にデータを追加していくのは、挿入ソートの説明です。 クイックソートは挿入ではなく、基準値による分割を繰り返します。 2：× 最小値を選んで取り出す操作を繰り返すのは、選択ソートの説明です。 クイックソートは最小値探索ではなく、グループ分割で整列します。 3：○ 基準値より小さいグループと大きいグループに分け、各グループでまた基準値を選んで分割しています。 これはクイックソートの処理そのものです。 4：× 隣り合うデータの比較と入替えを繰り返すのは、バブルソートの説明です。 クイックソートは隣同士ではなく、基準値との大小でデータを振り分けます。 【ポイント】 挿入・選択・バブルの各ソートは計算量O(n²)、クイックソートは平均O(n log n)です。 クイックソートは、基準値の選び方が悪いと最悪O(n²)になる点も覚えておきましょう。