令和元年度秋期 応用情報技術者試験 午前 問8

正解：イ

AI解説

分割統治法とは、問題を再帰的に小さな部分問題に分割して個別に解き、それらを統合することで全体の解を得る手法である。クイックソートは基準値(ピボット)を用いてデータを2つの部分列に分割し、それぞれを再帰的に整列することで全体を整列する分割統治型のアルゴリズムである。 ア: 基数ソートは各桁の値ごとにバケットに振り分けて整列する手法であり、分割統治法ではなく分配法に分類される。 イ: クイックソートはピボットを基準にデータを分割し、各部分を再帰的に整列する分割統治法の代表例であり正解である。 ウ: 選択ソートは未整列部分から最小(または最大)値を選び出して順に並べる単純な比較ソートであり、分割統治法ではない。 エ: 挿入ソートは整列済み部分に新しい要素を適切な位置に挿入していく単純な比較ソートであり、分割統治法ではない。 💡 分割統治法を使う代表的な整列アルゴリズムは「クイックソート」と「マージソート」であり、この2つはセットで覚えておくとよい。