基本情報技術者試験 令和8年度 科目A 公開問題 問2

【正解】ウ

クイックソートは、データ列から基準値であるピボットを一つ選び、ピボットより小さい値のグループと、大きい値のグループに分割する整列方法です。分割後の各グループについても同じ処理を再帰的に行い、グループが十分に小さくなるまで繰り返します。例えば、基準値を5とした場合、3や2は小さい側、8や7は大きい側に分けられます。この分割を繰り返すことで、データ全体が整列されます。したがって、ウが正解です。

アの説明は誤りです。これは挿入ソートの説明です。挿入ソートは、整列済みの部分の適切な位置へ、未整列のデータを一つずつ挿入していく方法です。

イの説明は誤りです。これは選択ソートの説明です。選択ソートは、未整列部分から最小値又は最大値を選び、先頭又は末尾へ順に配置します。

エの説明は誤りです。これはバブルソートの説明です。バブルソートは、隣接するデータを比較して順序が逆なら交換する処理を繰り返し、値を端へ移動させます。

【ポイント】 クイックソートは「基準値による分割」と「分割後の再帰処理」が目印です。 平均的な時間計算量はO（n log n）ですが、ピボットの選び方が悪い場合はO（nの2乗）になることがあります。