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

解説

正解は1です。 代表的な整列（ソート）アルゴリズムの特徴を区別する問題です。 クイックソートは、基準値（ピボット）より大きいグループと小さいグループに分ける操作を、再帰的に繰り返す方式です。 【選択肢別解説】 1：○ 基準となる要素を選び、大小の集合に分割する操作を繰り返すのは、クイックソートの説明です。 平均計算量はO(n log n)で、高速な整列法として知られます。 2：× 未整列の中から最も小さい要素を順次取り出して並べるのは、選択ソート（単純選択法）の説明です。 クイックソートは最小値を探すのではなく、基準値で分割します。 3：× 取り出した要素を、整列済みの集合の適切な位置に挿入していくのは、挿入ソート（単純挿入法）の説明です。 4：× 隣り合う要素を比較し、逆順なら交換する操作を繰り返すのは、バブルソート（隣接交換法）の説明です。 【ポイント】 「分割」はクイックソート、「最小値の選択」は選択ソート、「挿入」は挿入ソート、「隣接交換」はバブルソートと、キーワードで対応付けて覚えます。 クイックソートは最悪の場合、計算量がO(n²)になる点も頻出です。