BohYoh.com《第２種情報処理技術者試験》1996年度＝平成8年度・春期午前問16

第２種情報処理技術者試験

1996年度＝平成8年度・春期

午前

問16

　整数値からなるn個（ただし、n≧2）のデータが、配列Ｔに格納されている。次の流れ図は、それらのデータを交換法を用いて昇順に整列する処理を示す。流れ図中のａに入れるべき適切な条件はどれか。

ア　T(j) ＜ T(j＋1)	イ　T(j) ＜ T(j－1)
ウ　T(j) ＝ T(j－1)	エ　T(j) ＞ T(j＋1)
オ　T(j) ＞ T(j－1)

解答

　イ

解説

　バブルソートでは、隣り合うデータを比較し、必要であれば交換を行うという一連の操作（パス）をn - 1回行います（ループＡ）。
　１回のパスでの比較・交換の一例を以下に示します。

　　　┌─┬─┬─┬─┬─┬─┐ 　　　│５│４│１│３│６│２│　　　　最初の状態　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│５│１│３│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│５│２│３│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│２│５│３│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換の必要なし　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│２│５│３│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│４│２│５│３│６│ 　　　└─┴─┴─┴─┴─┴─┘

　このように、着目している値の対である、末尾側のT(j)の値が、先頭側T(j-1)の値より小さいときのにみ交換を行います。
※１パス目が終了した時点で、最も小さい値が配列の先頭に位置することになります。このパスをn-1回繰り返すとソートが完了します。