平成14年春期試験問題 午前問14
問14解説へ
四つの数の並び(4，1，3，2)を，ある整列アルゴリズムに従って昇順に並べ替えたところ，数の入替えは次のとおり行われた。この整列アルゴリズムはどれか。
(1，4，3，2)
(1，3，4，2)
(1，2，3，4)
(1，4，3，2)
(1，3，4，2)
(1，2，3，4)
- クイックソート
- 選択ソート
- 挿入ソート
- バブルソート
広告
解説
それぞれの整列アルゴリズムは次のような手順で整列を行います。
- クイックソート
- 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する。同様にして、グループの中で基準値を選び、それぞれのグループを分割する。この操作を繰り返してソートを行うアルゴリズム
- 選択ソート
- 未整列部分の中で最小値を求め、最小値の要素を未整列部分の先頭要素と入れ替えることを繰り返してソートを行うアルゴリズム
- 挿入ソート
- 未整列部分の先頭から要素を取り出し、取り出した要素を整列済み部分の順序関係を保つよう挿入することを繰り返してソートを行うアルゴリズム
- バブルソート(基本交換法)
- 全ての要素に関して，隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なうアルゴリズム
- 問題文の整列手順は基準値によってグループ分けされていないのでクイックソートではないとわかります。
- 選択ソートでは次のような整列手順になります。
(4，1，3，2)
(1，4，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)
(1，4，3，2) 4＞1なので交換
(1，3，4，2) 4＞3なので交換
(1，3，2，4) 4＞2なので交換
(1，2，3，4) 3＞2なので交換
バブルソートでは問題文の手順と異なります。
広告