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

正解

イ. クイックソート

正答率 55.1%（1,094人中 603人が正解）

問題の解説

分割統治法は、問題を小さな部分問題に分けて解き、その結果を組み合わせる考え方である。クイックソートは、基準値より小さいグループと大きいグループにデータを分け、それぞれを同じ手順で再帰的に整列するので、この考え方に当たる。

選択肢ごとの解説

• アキーの桁ごとにデータを振り分けることを繰り返して整列する方法で、部分問題に分けて解くものではない。
• イ正しい。基準値でデータを二つの部分に分け、それぞれを同じ手順で整列するので、分割統治を利用している。
• ウ未整列の部分から最小値を選んで先頭に置くことを繰り返す方法で、問題の分割は行わない。
• エ未整列の要素を、整列済みの部分の適切な位置に挿入していく方法で、問題の分割は行わない。