あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。 整列に使ったアルゴリズムはどれか。
状態0 3, 5, 9, 6, 1, 2
状態1 3, 5, 6, 1, 2, 9
状態2 3, 5, 1, 2, 6, 9
・
・
・
状態N 1, 2, 3, 5, 6
ア | クイックソート |
イ | 挿入ソート |
ウ | バブルソート |
エ | ヒープソート |
答え ウ
【解説】
問題のアルゴリズムはデータの先頭から、次のデータと大きさを比較して次のデータが小さければ入れ替える作業を行っているので、これはバブルソート(ウ)になる。
ア | クイックソートは、未整列のデータ列を適当に選択したデータより大きいデータ、小さいデータに分割しながら整列するアルゴリズムで、分割統治法を適用しています。(×) |
イ | 挿入ソートは、未整列のデータ列から最少(最大)のデータを探しだしてデータ列の先頭に持ってきて、次に2番目以降のデータに対しこれを繰り返す整列アルゴリズムです。(×) |
ウ | バブルソートは、隣り合ったデータの比較と入替えを繰り返すことによって、小さな(大きな)値のデータを次第に端の方に移していく整列アルゴリズムです。(〇) |
エ | ヒープソートは、未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す作業を繰り返す整列アルゴリズムです。(×) |
【キーワード】
・整列