BohYoh.com《第２種情報処理技術者試験》1995年度＝平成7年度・秋期午前問12

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

1995年度＝平成7年度・秋期

午前

問12

　データ列の隣り合う要素の値を比較し、小さいほうが右にあれば交換する。この操作をデータ列の左から末尾まで繰り返すのを１回のパスとする。
　次のデータ列で２回パスを繰り返したときのデータ列の内容を示しているものはどれか。

┌─┬─┬─┬─┬─┬─┐ │５│４│１│３│６│２│ └─┴─┴─┴─┴─┴─┘

　　　┌─┬─┬─┬─┬─┬─┐ 　ア　│１│３│２│４│５│６│ 　　　└─┴─┴─┴─┴─┴─┘

　　　┌─┬─┬─┬─┬─┬─┐ 　イ　│１│３│４│２│５│６│ 　　　└─┴─┴─┴─┴─┴─┘

　　　┌─┬─┬─┬─┬─┬─┐ 　ウ　│１│４│５│３│２│６│ 　　　└─┴─┴─┴─┴─┴─┘

　　　┌─┬─┬─┬─┬─┬─┐ 　エ　│４│１│５│３│２│６│ 　　　└─┴─┴─┴─┴─┴─┘

　　　┌─┬─┬─┬─┬─┬─┐ 　オ　│４│１│５│３│６│２│ 　　　└─┴─┴─┴─┴─┴─┘

解答

　イ

解説

　バブルソートでは、隣り合うデータを比較し、必要であれば交換を行うという一連の操作（パス）をn - 1回行います。
　この問題では、整列の作業を最後まで行わずに、2パスだけ行った時点でのデータの並びがどうなるかを問う問題です。

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

※１パスが終了した時点で、最も大きい値が配列の最後に位置しますから、２パス目の最後の比較・交換作業は省略することができます。