分割統治を利用した整列法
出典: 令和元年度 秋期 応用情報技術者試験 午前 問8 (IPA)
分割統治を利用した整列法はどれか。
- ア 基数ソート
- イ クイックソート
- ウ 選択ソート
- エ 挿入ソート
正解と解説を見る
正解: イ
- ア: 基数ソートは、桁ごとに分けて並べ直していく方法で、分割統治法ではありません。
- イ: 基準値で 2 つのグループに分け、それぞれを再帰的に整列するクイックソートは、分割統治法を使っています。正しい答えです。
- ウ: 選択ソートは、未整列の部分から最小値を探して前に移す方法です。
- エ: 挿入ソートは、整列済みの部分の正しい位置に 1 つずつ挿入していく方法です。
ポイント
- 分割統治法: 大きな問題を小さな問題に分けて解き、その結果を組み合わせて全体を解く考え方です。
- クイックソート は、基準値より小さいグループと大きいグループに分け、それぞれを同じ方法で整列していくので、分割統治法を使っています (マージソートも同じです)。