基本情報技術者 平成14年春期 午前問14

午前問14

四つの数の並び(4,1,3,2)を,ある整列アルゴリズムに従って昇順に並べ替えたところ,数の入替えは次のとおり行われた。この整列アルゴリズムはどれか。

(1,4,3,2)
(1,3,4,2)
(1,2,3,4)
  • クイックソート
  • 選択ソート
  • 挿入ソート
  • バブルソート

分類

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

正解

解説

それぞれの整列アルゴリズムは次のような手順で整列を行います。
クイックソート
適当な基準値を選び,それより小さな値のグループと大きな値のグループにデータを分割する。同様にして,グループの中で基準値を選び,それぞれのグループを分割する。この操作を繰り返してソートを行う手法。
選択ソート
未整列部分の中で最小値を求め,最小値の要素を未整列部分の先頭要素と入れ替えることを繰り返すことによってソートを行う手法。
挿入ソート
未整列部分の先頭から要素を取り出し,取り出した要素を整列済み部分の順序関係を保つよう挿入することを繰り返すことでソートを行う手法。
バブルソート(基本交換法)
全ての要素に関して,隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう手法。
  • 問題文の整列手順は基準値によってグループ分けされていないのでクリックソートではないとわかります。
  • 選択ソートでは次のような整列手順になります。

    (4,1,3,2)
    (14,3,2) 1と4を交換
    (1,2,3,4) 2と4を交換

    選択ソートでは問題文の手順と異なります。
  • 正しい。
    挿入ソートでは次のような整列手順になります。

    (4,1,3,2) (4を整列済みとする)
    (1,4,3,2) 4の前に1を挿入する。(1,4が整列済み)
    (1,3,4,2) 1,4の間に3を挿入する。(1,3,4が整列済み)
    (1,2,3,4) 1,3の間に2を挿入する。(整列完了)

    問題文の手順と同じになります。
  • バブルソートでは次のような整列手順になります。

    (4,1,3,2) 
    (14,3,2) 4>1なので交換
    (1,34,2) 4>3なので交換
    (1,3,24) 4>2なので交換
    (1,23,4) 3>2なので交換

    バブルソートでは問題文の手順と異なります。
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop