分割統治を利用した整列法はどれか。
ア | 基数ソート |
イ | クイックソート |
ウ | 選択ソート |
エ | 挿入ソート |
答え イ
【解説】
分割統治法とは、そのままでは解決できない大きな問題を小さな問題に分けて、小さな問題を一つ一つ解いて、大きな問題を解く手法です。
ア | 基数ソートは、データの桁ごとに並べ替えていく整列アルゴリズムです。 (バケットソートを改良したものです。) |
イ | クイックソートは、未整列のデータ列を適当に選択したデータより大きいデータ、小さいデータに分割しながら整列するアルゴリズムで、分割統治法を適用しています。 |
ウ | 選択ソートは、未整列のデータ列から最少(最大)のデータを探しだしてデータ列の先頭に持ってきて、次に2番目以降のデータに対しこれを繰り返す整列アルゴリズムです。 |
エ | 挿入ソートは、未整列のデータ列の1番目と2番目のデータを並べ替え、次に3番目のデータを正しい位置に挿入するというのを繰り返す整列アルゴリズムです。 |
【キーワード】
・整列(ソート)