対象試験と出題頻度
バブルソート（基本交換法）は、基本情報技術者・応用情報技術者で出題されるテーマです。
整列アルゴリズムの比較問題として定番化しており、「シェルソート」「クイックソート」「ヒープソート」との違いを正確に区別できるかが問われます。
FE R4年度 科目A免除 問8、AP R3秋期 午前問5、AP H25秋期 午前問9など、複数の試験区分で繰り返し出題されています。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★☆☆☆
ランクC（応用）余裕があれば覚える
用語の定義
情報処理試験を勉強していると、「ソートの種類が多すぎて、バブルソートと他の整列法の区別がつかない」と混乱しがちです。
バブルソート（Bubble Sort：基本交換法）とは、一言で言うと
「隣り合う要素を比較し、順序が逆であれば交換する操作を繰り返して配列全体を整列するアルゴリズム」
のことです。
イメージとしては、「背の順の整列で、隣同士を見比べて順番が違えば入れ替える作業を、端から端まで何往復も繰り返す」こと。
体育の授業で「隣の人と背を比べて、高い方が後ろに移動して」を列全体に繰り返せば、最終的に全員が背の順に並びます。これがバブルソートの考え方です。
名前の由来は、値の小さい要素が泡（バブル）のように配列の先頭へ浮かび上がっていく様子から来ています。
📊 バブルソートの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Bubble Sort |
| 別名 | 基本交換法、単純交換法、隣接交換法 |
| 時間計算量 | 平均・最悪ともに O(n²) |
| 比較回数 | n(n−1)/2 回（nは要素数） |
| 安定性 | 安定ソート（同じ値の要素の順序が保たれる） |
詳細解説
整列（ソート）は、データを昇順や降順に並べ替える処理であり、プログラミングの最も基本的な操作の一つです。
バブルソートは、その中でも最もシンプルな手法として位置づけられます。
動作の仕組み
配列の末尾から先頭に向かって、隣り合う2つの要素を比較します。
左の要素が右の要素より大きければ交換し、そうでなければそのまま進みます。これを1回走査（パス）すると、最も小さい値が配列の先頭に確定します。2回目のパスでは2番目に小さい値が確定し、n−1回のパスで全体が整列されます。
▶ 図解：バブルソートの動作例 [5, 3, 8, 1]（クリックで展開）
【パス1】先頭の値を確定させる
初期状態 ：5381
比較① 8 と 1 → 8 > 1 なので交換：5318
比較② 3 と 1 → 3 > 1 なので交換：5138
比較③ 5 と 1 → 5 > 1 なので交換：1538
→ 1 が先頭に確定
【パス2】2番目の値を確定させる
比較① 3 と 8 → 3 < 8 なのでそのまま
比較② 5 と 3 → 5 > 3 なので交換：1358
→ 3 が2番目に確定
【パス3】3番目の値を確定させる
比較① 5 と 8 → 5 < 8 なのでそのまま
→ 整列完了：1358
▶ 擬似コード：バブルソートの実装（クリックで展開）
IPAの科目B（旧午後試験）で出題される擬似言語に近い形で記述します。
○ BubbleSort(整数型の配列: A, 整数型: n)
整数型: i, j, temp
for (i を 1 から n-1 まで 1 ずつ増やす)
for (j を n から i+1 まで 1 ずつ減らす)
if (A[j] < A[j-1])
temp ← A[j]
A[j] ← A[j-1]
A[j-1] ← temp
endif
endfor
endfor外側のループ（i）がパス回数を制御し、内側のループ（j）が各パスでの比較範囲を制御します。パスが進むごとに比較範囲が1つ縮まるのがポイントです。
他の整列アルゴリズムとの比較
バブルソートを正しく理解するには、他の基本ソートと「何を基準に並べ替えるか」で整理するのが近道です。
| アルゴリズム | 動作の特徴 | 平均計算量 |
|---|---|---|
| バブルソート （基本交換法） |
隣り合う要素を比較・交換する | O(n²) |
| 選択ソート （基本選択法） |
未整列部分から最小値を探して先頭と交換する | O(n²) |
| 挿入ソート （基本挿入法） |
未整列の要素を整列済み部分の適切な位置に挿入する | O(n²) |
| シェルソート | 一定間隔おきの部分列を整列し、間隔を詰めていく | O(n^1.25)～ |
| クイックソート | 基準値（ピボット）で分割を再帰的に繰り返す | O(n log n) |
| ヒープソート | 未整列部分を順序木（ヒープ）にし、最小値を取り出す | O(n log n) |
ここだけは確実に押さえてください。バブルソートは「隣接する要素の比較・交換」が他の手法と決定的に異なるキーワードです。
シェルソートは「間隔おき」、クイックソートは「基準値で分割」、ヒープソートは「順序木」と整理すれば、選択肢で迷うことはありません。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 バブルソートの核心を3行で
・隣り合う要素を比較し、順序が逆なら交換する操作を繰り返す整列法
・比較回数は n(n−1)/2 回で、時間計算量は O(n²)
・シェルソートは「間隔おき」、クイックソートは「基準値で分割」、ヒープソートは「順序木」と区別する
試験ではこう出る！
バブルソートは、整列アルゴリズムの説明を選ばせる問題やトレース問題として各試験区分で繰り返し出題されています。
出題パターンは大きく2つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE R4年度 科目A免除 問8 |
4つのソートアルゴリズムの説明文からバブルソートを選ぶ問題。 | ・「隣り合う要素を比較・交換」が正解 ・シェルソート・クイックソート・ヒープソートがひっかけ |
| AP R3秋期 午前 問5 |
FE R4年度と同一の問題構成（流用問題）。 | ・FE・AP間で同じ問題が出回る典型例 ・選択肢の構成も完全に同一 |
| AP H25秋期 午前 問9 |
配列 [21,5,53,71,3,17] をバブルソートで整列するとき、交換回数を答える問題。 | ・流れ図を読み取り、各パスの交換回数をトレースする力が必要 ・正解は8回 |
| FE H19春期 午前 問14 |
バブルソートのアルゴリズムを示し、1回目のパス終了時に成り立つ状態を選ぶ問題。 | ・パス1回で先頭に最小値が確定する動作を理解しているか |
📝 IPA試験での出題パターン
パターン1：「バブルソートの説明を選べ」
4つの整列アルゴリズムの説明文が並び、バブルソートに該当するものを選ぶ形式。ひっかけとしてシェルソート（間隔おきに部分列を整列）やヒープソート（順序木から最小値を取り出す）の説明が紛れ込む。キーワードは「隣り合う要素」「比較・交換」。
パターン2：「交換回数を求めよ」
具体的な配列が与えられ、流れ図やアルゴリズムに従ってトレースし、交換が何回発生するかを数える問題。科目B（旧午後）でも擬似言語によるソート実装として出題される。
試験ではここまででOKです。計算量 O(n²) の証明過程や改良版（カクテルシェーカーソート等）まで問われることはないので、深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. バブルソートの説明として、最も適切なものはどれでしょうか？
- A. 中間的な基準値を決めて、それより大きな値と小さな値の区分に振り分け、各区分で同様の操作を再帰的に繰り返す。
- B. ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、間隔を詰めて同様の操作を行い、間隔が1になるまで繰り返す。
- C. 隣り合う要素を比較して、大小の順が逆であれば入れ替えるという操作を繰り返す。
正解と解説を見る
正解：C
解説：
バブルソートは、隣り合う要素を比較し、大小の順が逆であれば交換する操作を繰り返して整列するアルゴリズムです。「隣り合う」「比較・交換」の2語が判断基準になります。
選択肢Aはクイックソートの説明です。基準値（ピボット）で区分を分割し、再帰的に処理するのが特徴であり、隣接要素の交換ではありません。選択肢Bはシェルソートの説明です。一定間隔の部分列を整列してから間隔を縮めていく手法であり、最初から隣同士を比較するわけではありません。
よくある質問（FAQ）
Q. バブルソートは実務で使われていますか？
ほとんど使われません。データ件数が増えると処理時間が急激に増加するため、実務ではクイックソートやマージソート、あるいはプログラミング言語の標準ライブラリに組み込まれた最適化済みのソート関数を使うのが一般的です。バブルソートは「アルゴリズムの基本を学ぶための教材」としての意味合いが強く、試験対策として仕組みを理解しておけば十分です。
Q. 「安定ソート」と「不安定ソート」の違いは何ですか？
同じ値を持つ要素が複数あるとき、整列後もその相対的な順序が保たれるソートを「安定ソート」と呼びます。バブルソート・挿入ソート・マージソートは安定ソートです。一方、クイックソート・ヒープソート・選択ソートは不安定ソートであり、同じ値の要素の順序が入れ替わる場合があります。
Q. バブルソートを高速化する方法はありますか？
あります。あるパスで一度も交換が発生しなかった場合、配列は既に整列済みなので処理を打ち切る「早期終了」の改良が代表的です。この改良を加えると、最良ケース（初めから整列済みの場合）の計算量はO(n)に改善されます。ただし、最悪ケースのO(n²)は変わらないため、根本的な性能改善にはなりません。
Q. 科目Bでバブルソートの擬似コードが出たとき、何を意識すればよいですか？
まずは二重ループの構造を把握してください。外側ループがパス回数、内側ループが比較範囲を制御しています。次に、ループ変数が「増える方向か減る方向か」を確認します。先頭から末尾へ走査するパターンと、末尾から先頭へ走査するパターンの2種類があり、比較対象が A[j] と A[j+1] なのか A[j] と A[j-1] なのかが変わります。問題文の流れ図や擬似言語を3〜4要素の小さい配列でトレースすれば、動作を正確に追えます。
