データベーススペシャリスト令和5年秋期 午前T 問3

問3

あるデータ列を整列したら状態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,9
  • クイックソート
  • 挿入ソート
  • バブルソート
  • ヒープソート
  • [出典]
  • 応用情報技術者
    令和5年秋期 問6と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

バブルソート(基本交換法)は、データ列中の隣り合った要素同士を比較し、順序が合っていなれば交換する操作を繰り返して整列するアルゴリズムです。1回の操作ごとに、未整列データのうち最大値または最小値が確定していきます。
am1/06.gif/image-size:211×406
状態0から状態1への1回目の整列で、最大値の"9"が正しい位置である末尾まで移動しています。そして、2回目の整列では、2番目に大きい"6"が末尾の一つ前に移動しています。データ列の端から順にひとつずつ確定していく流れから、バブルソートであるとわかります。

したがって「ウ」が正解です。
  • クイックソートは、整列対象のデータ群をある基準値以下のグループと基準値以上のグループに分割し、さらに分割後の各グループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです。状態の変化を見ても値の大小でグループ化されている様子がないので違うとわかります。
    am1/06_1.gif/image-size:325×203
  • 挿入ソートは、未整列部分の先頭から要素を取り出し、取り出した要素を整列済み部分の順序関係を保つよう挿入することを繰り返して整列するアルゴリズムです。末尾から整列していく場合、末尾が[2]→[1, 2]→[1, 2, 6]と確定していくはずですが、状態1で9が末尾に移動していることから違うとわかります。
    am1/06_2.gif/image-size:211×406
  • 正しい。未整列データのうち最も大きい値を端に寄せることを繰り返しているので、バブルソートであるとわかります。
  • ヒープソートは、未整列データを「親の値≦子の値」(または「親の値≧子の値」)の関係をもつ順序木として表現し、整列後の根の値(最小値または最大値)を取り出すことを繰り返して整列を行う方法です。未整列データがヒープ木として表現されている様子がないので違うとわかります。
© 2016-2024 データベーススペシャリストドットコム All Rights Reserved.

Pagetop