ITパスポート 令和5年度 問60：algorithmに関する問題

答えは a「1,2,3,4」 です。

このプログラムは、トランプを「小さい順」に並べ替える作業をしています。やり方は、となり同士を比べて「左が大きければ入れ替える」をくり返すだけ。これを何回もやると、最後はきれいに小さい順に並びます。

スタートは {2,4,1,3} のバラバラ。順番にとなりを比べて入れ替えていくと、最後は {1,2,3,4} になります。

👉 覚え方：「となりと比べて大きい方を後ろへ」をくり返す＝小さい順に整列。

ほかの選択肢：b/cは途中のグチャグチャな並び、dは逆の大きい順。最後まで動かすと“ちゃんと小さい順”になります。

なぜこれが正解か

正解は a「1,2,3,4」。このプログラムはバブルソート（昇順）。隣り合う要素を比較し、左が右より大きければ交換する操作を繰り返す。{2,4,1,3}に対し:

• 1巡目: 2,4比較→そのまま／4,1交換→2,1,4,3／4,3交換→2,1,3,4
• 2巡目: 2,1交換→1,2,3,4／2,3そのまま
• 3巡目: 1,2そのまま

最終結果は 1,2,3,4。

各選択肢の解説

• b 1,3,2,4・c 3,1,4,2：途中経過に似せたダミー。完走させると不一致。
• d 4,3,2,1：降順。比較条件が逆（< なら降順）のときの結果。

覚え方・ひっかけ注意

`integerArray[m] > integerArray[m+1]` で交換＝大きいものが右（後ろ）へ押し出される＝昇順。「>なら昇順、<なら降順」とセットで暗記。手で1巡ずつ追うとミスが減る。

理論的背景

本問のプログラムはバブルソート（Bubble Sort）の典型的な実装であり、外側ループが整列済み要素数（確定済み末尾要素数）を管理し、内側ループが比較対象範囲の左端から右への隣接比較・交換を繰り返す。アルゴリズムの動作原理は「各パスで未整列部分の最大要素が右端（末尾）へ浮かび上がる」というバブリング（bubbling）の繰り返しであり、k回目のパス終了後には後ろからk個の要素が確定（昇順の場合、最大値から順に正しい位置に収まる）する。

比較条件 `integerArray[m] > integerArray[m + 1]` は「左側が右側より大きければ交換する」を意味し、交換によって大きい値が右へ移動する。この操作を全パス完走させると昇順（小→大）ソートが実現される。不等号の向きを逆（`<`）にすれば降順ソートとなる点も試験の頻出知識である。

内側ループの上限が `(integerArrayの要素数 - n)` となっている点は最適化であり、nパス目終了時点で後ろn要素が確定済みなので比較が不要になる部分を除外している。この最適化がなくても（上限を固定でも）最終的な結果は同じだが、比較回数が削減される。

詳細なトレース

初期配列：{2, 4, 1, 3}（要素数4）

n=1パス目（内側ループm=1〜3）：

• m=1：Array[1]=2 vs Array[2]=4 → 2<4なので交換なし → {2,4,1,3}
• m=2：Array[2]=4 vs Array[3]=1 → 4>1なので交換 → {2,1,4,3}
• m=3：Array[3]=4 vs Array[4]=3 → 4>3なので交換 → {2,1,3,4}

→ パス1終了後：{2,1,3,4}（最大値4が末尾に確定）

n=2パス目（内側ループm=1〜2）：

• m=1：Array[1]=2 vs Array[2]=1 → 2>1なので交換 → {1,2,3,4}
• m=2：Array[2]=2 vs Array[3]=3 → 2<3なので交換なし → {1,2,3,4}

→ パス2終了後：{1,2,3,4}（後ろ2要素確定）

n=3パス目（内側ループm=1〜1）：

• m=1：Array[1]=1 vs Array[2]=2 → 1<2なので交換なし → {1,2,3,4}

→ 最終結果：1,2,3,4

実務での使われ方

バブルソートはO(n²)の時間計算量を持ち、実用的なシステムでの大規模データソートには使用されない（入力が数百万件規模になると処理時間が膨大になる）。実際のプログラムではC++のstd::sort（平均O(n log n)のイントロソート）、JavaのArrays.sort（Timソート：安定ソート・O(n log n)）、Pythonのリストのsortメソッドとsortedビルトイン関数（Timソート）が使用される。

バブルソートが実用されない理由はその非効率さだが、改良版として「早期終了（一パスで交換が1回もなければ整列済みとして終了）」を加えた改良バブルソートはベストケースO(n)となり、ほぼ整列済みのデータに対して効率的になる。教育・アルゴリズム学習目的では、挙動が直感的に理解しやすいことから入門教材として広く使われる。

試験での位置づけ

ITパスポートのテクノロジ系・アルゴリズム分野では、疑似言語（IAQ言語）のトレース問題・穴埋め問題が配点の高い頻出問題として位置づけられる。バブルソートの識別と正確なトレースが問われるパターンは毎年出題されており、「二重ループ＋隣接比較＋条件による交換」という構造を見たらバブルソートと即座に識別できるようにしておくことが対策の第一歩である。

選択肢の設計として、選択肢b（1,3,2,4）・c（3,1,4,2）は「パスを途中で止めた中間状態」に近い値を使っており、トレースを最後まで完走させない受験者を誘導する設計になっている。選択肢d（4,3,2,1）は不等号の向きを逆（降順）と誤読した場合の結果である。これらのひっかけを防ぐには、一行一行丁寧にトレースし、途中経過と最終結果を混同しないことが重要である。

選択肢の発展補足

ソートアルゴリズムの比較を整理すると、基本情報技術者試験での頻出内容となる。

• バブルソート：O(n²)、安定ソート、実装シンプル。本問の対象。
• 選択ソート：O(n²)、不安定ソート（実装による）、最小値を選んで末尾と交換するパターン。
• 挿入ソート：O(n²)（最良O(n)）、安定ソート、ほぼ整列済みデータに強い。
• クイックソート：平均O(n log n)・最悪O(n²)、不安定ソート（一般的実装）、実用最速。
• マージソート：O(n log n)、安定ソート、外部メモリを必要とするが安定性が重要な場面で有用。
• ヒープソート：O(n log n)、不安定ソート、最悪でもO(n log n)を保証。

「安定ソート」とは等値の要素の相対順序が入力後も保たれるソートであり、複数キーでのソートやユーザー体験に影響する場合に重要となる。Timソート（Python・Javaが採用）は挿入ソートとマージソートを組み合わせた安定ソートで実装され、実データに多いパターン（部分的に整列済み）に最適化されている。