応用情報技術者試験 応用情報技術者試験 令和元年度秋期 午前 問8: 分割統治を利用した整列法はどれか。

問題本文

分割統治を利用した整列法はどれか。

選択肢

• ア.基数ソート
• イ.クイックソート
• ウ.選択ソート
• エ.挿入ソート

正解

イ. クイックソート

解説

分割統治法とは、問題をいくつかの部分問題に分割し、各部分を解いてから全体を統合する手法で、整列法ではクイックソートとマージソートが該当する。クイックソートは基準値(ピボット)より小さいグループと大きいグループに分割し、各グループをさらに同様に分割して整列する典型的な分割統治法である。よって正解は イ である。

選択肢ごとの解説

• ア.基数ソートはキーの桁(基数)ごとにバケツへ振り分けて整列する分配法であり、分割統治法ではないので誤り。
• イ.クイックソートは基準値で小さい側と大きい側に分割し、各グループを再帰的に分割・整列する分割統治法そのものであり、正しい。
• ウ.選択ソートは未整列部分から最小値を探して先頭と交換する操作を繰り返す手法で、問題を分割せず分割統治法ではないので誤り。
• エ.挿入ソートは要素を一つずつ整列済みの適切な位置へ挿入していく手法で、分割統治法ではないので誤り。