第２種情報処理技術者試験 2000年度 ＝ 平成12年度・秋期 午前 問15

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

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

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

解答

　イ

解説

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

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

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

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

BohYoh.comトップページへ