修了試験 2024-06-09実施分 基本情報技術者試験 問6

解説

正解は1です。 代表的な整列（ソート）アルゴリズムの特徴を区別する問題です。 クイックソートは、基準値（ピボット）で集合を分割する操作を繰り返す方式です。 【選択肢別解説】 1：○ 基準となる要素より大きい集合と小さい集合に分ける操作を、分割後の各集合に再帰的に繰り返します。 これはクイックソートの説明です。 平均計算量はO(n log n)で、実用上高速な方式として知られます。 2：× 最も小さい要素を順に選んで取り出すのは、選択ソートです。 クイックソートは分割を繰り返す点が異なります。 3：× 取り出した要素を整列済みの集合の適切な位置に挿入するのは、挿入ソートです。 4：× 隣り合う要素を比較して逆順なら交換するのは、バブルソート（交換法）です。 【ポイント】 選択ソート・挿入ソート・バブルソートは計算量O(n²)の基本整列法です。 クイックソートは分割統治の考え方で、最悪の場合はO(n²)になる点もあわせて覚えましょう。