修了試験 2021-01-24実施分 基本情報技術者試験 問8

解説

正解は1です。 クイックソートは、基準値（ピボット）を選んで、それより小さいグループと大きいグループに分割する操作を再帰的に繰り返す整列法です。 平均計算量はO(n log n)で、実用上高速な整列法として知られています。 【選択肢別解説】 1：○ 基準となる要素で大小2つの集合に分割し、それを繰り返すのはクイックソートの説明です。 2：× 最も小さい要素を順次取り出して整列するのは、選択ソート（基本選択法）の説明です。 3：× 取り出した要素を整列済みの集合の適切な位置に挿入していくのは、挿入ソート（基本挿入法）の説明です。 4：× 隣り合う要素を比較し、逆順なら交換していくのは、バブルソート（基本交換法）の説明です。 【ポイント】 代表的な整列法は「分割」ならクイックソート、「最小値の選択」なら選択ソート、「挿入」なら挿入ソート、「隣接交換」ならバブルソートと対応させて覚えます。 クイックソートは最悪の場合O(n²)になる点も押さえておきます。