「応用情報技術者試験/令和元年秋期午前問8」分割統治

問題

出典:応用情報技術者令和元年秋期午前問8

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

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

解説

分割統治とは、大きなグループを小さく分けて統治し、その小さな問題を解決した結果を統合していき、最終的な答えを導き出す方法である。

これが分かっても、選択肢のソートがどんなものか理解していないと、この問題を解くのは難しい。

基数ソートとは、進数の数分のバケツを用意し、
「データの下位1桁の値別」にバケツに割り振る。
「データの下位2桁の値別」にバケツに割り振る。
「データの下位3桁の値別」にバケツに割り振る。
「データの下位4桁の値別」にバケツに割り振る。
・・・・
という風に下位の桁から値を観察し振り分けを行い、全てのデータの全ての桁で振り分けを行うと、ソートが完了しているという方法。
つまり、最初からグループは決められているので、分割統治とは関係がない。

クイックソートとは、基準値に従ってグループ分けを行い、そのグループの中でもさらに基準値に従ってグループを分けていき、ソートを実施するアルゴリズムである。
よって、これは分割統治である。

選択ソートとは、最小値または最大値を探して、それを配列の先頭要素と交換していくことでソートを行うアルゴリズム。

挿入ソートとは、リストの整列部分に対して新たな要素を適切な位置に挿入することでソートを行うアルゴリズム。

解答

正解:イ

アドセンス
改行

テックキャンプ