ITパスポート 2023年 問60

手続printArrayは配列を並べ替えて出力する問題【ITパスポート 解説】

正解の理由

解法ステップ

• 配列の要素番号は1から始まる（問題文の指定）。
• 外側のループ n は 1 から (要素数−1) まで回る。
• 内側のループ m は 1 から (要素数 − n) まで回り、integerArray[m] と integerArray[m+1] を比較して大きければ入れ替える。
• これを繰り返すと配列は昇順に整列する（バブルソートの働き）。

• m=1: 比較 2 と 4 → 2 > 4? いいえ → {2,4,1,3}
• m=2: 比較 4 と 1 → 4 > 1? はい → 入れ替え → {2,1,4,3}
• m=3: 比較 4 と 3 → 4 > 3? はい → 入れ替え → {2,1,3,4}

• m=1: 比較 2 と 1 → 2 > 1? はい → 入れ替え → {1,2,3,4}
• m=2: 比較 2 と 3 → 2 > 3? いいえ → {1,2,3,4}

• m=1: 比較 1 と 2 → 1 > 2? いいえ → {1,2,3,4}

選択肢別の誤答解説

• ア（1,2,3,4）: 正解。上の手順どおり最終的に昇順に整列する。
• イ（1,3,2,4）: これは一部だけ入れ替わった状態です。完全に昇順になっていないため誤りです。バブルソートは複数回のパスで確実に並べ替えるため、この途中状態で終了することはありません。
• ウ（3,1,4,2）: 元の並び {2,4,1,3} を部分的にランダムに入れ替えたものです。与えられた交換規則（隣接比較で大きければ交換）からはこの順序にはなりません。
• エ（4,3,2,1）: これは降順（大きい順）です。問題の比較は「大きければ交換」しているため、大きい値は右側へ移動し最終的に昇順になります。従って降順にはなりません。

よくある誤解

1. 配列番号を0から始まると勘違いする
   • 問題は「要素番号は1から始まる」と明記しています。これはインデックス計算に影響します（この問題では m と m+1 の範囲が正しく動作することを保証します）。
2. 一回の内側ループ（1パス）で整列が終わると考える
   • バブルソートでは複数パスが必要です。最初のパスで最大値が末尾に移動しますが、残りはまだ乱れています。
3. 比較条件を逆に解釈する（大きければ交換 → 昇順になること）
   • 「大きければ右へ送る」処理は結果として昇順になります。逆の条件なら降順になります。

補足コラム

• バブルソートの特徴
  • 安定なソート：等しい要素の相対順序は保たれる（stable）。
  • インプレース：追加の大きな記憶領域を必要としない。
  • 計算量は一般に $O(n^2)$（要素数 $n$ に対して二重ループ）。小さい配列では理解しやすく使いやすいですが、大きなデータには不向きです。
• 最適化
  • 途中で交換が一度も起きなければ（既に整列済み）終了するようにすると平均処理を早められます。
• 名前の由来：大きな値がどんどん「泡（bubble）」のように末尾へ浮かんでいく様子に由来します。

# 1から始まるインデックスを意識せずにPythonで同じ動作をさせる例
arr = [2,4,1,3]
n = len(arr)
for i in range(n-1):
    for j in range(n-1-i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
print(','.join(map(str, arr)))  # 出力: 1,2,3,4

FAQ