バブルソート
まず結論
バブルソートは隣り合う要素を比較して順序が逆なら交換する操作を繰り返すソートです。大きい値が泡（バブル）のように浮き上がるイメージ。計算量はO(n²)で遅いですが、仕組みが単純で試験の頻出テーマです。
バブルソートの動き（1パスずつ）
配列 [5, 3, 4, 1, 2] を昇順にソートする：
初期状態
5
3
4
1
2
パス1：5が末尾に確定
3
4
1
2
5
パス2：4が確定
3
1
2
4
5
パス3：3が確定
1
2
3
4
5
完成！
1
2
3
4
5
擬似コード
// 配列 a[1..n] をバブルソートで昇順にソート
i を 1 から n-1 まで繰り返す // n-1パス
j を 1 から n-i まで繰り返す // 確定済みを除く
もし a[j] > a[j+1] ならば // 隣と比較
tmp ← a[j] // 一時変数で交換
a[j] ← a[j+1]
a[j+1] ← tmp
もし終わり
繰り返し終わり
繰り返し終わり
交換の3ステップ：tmp ← a[j] → a[j] ← a[j+1] → a[j+1] ← tmp
tmpという一時変数がないと上書きして値が消えてしまう！
tmpという一時変数がないと上書きして値が消えてしまう！
計算量と特徴
計算量
最良: O(n)（既ソート時・改良版）
平均・最悪: O(n²)
n=1000なら最大100万回の比較
特徴
✅ 実装が単純・わかりやすい
✅ 安定ソート（同じ値の順序保持）
❌ 大規模データには遅すぎる
🎯 試験での出方
- バブルソートの計算量 → O(n²)
- 「隣り合う要素を比較して交換する」→ バブルソート
- 1パス目終了後の配列の状態を問う問題（最大値が末尾に確定）
- 交換のための一時変数tmpの使い方
⚠️ よくある間違い
- 「交換にtmpは不要」→ ✗ tmp無しで直接代入すると元の値が消える
- 「n-1パス後に全要素が確定」→ ✓ n-1パス実行すれば完了する
- 「内側ループはn回全て回す」→ ✗ パスiでは確定済みを除くのでn-i回
✍️ 確認クイズ
Q1. バブルソートの最悪計算量はどれか。
✅ 正解は②。バブルソートは2重ループなのでO(n²)。マージソートやクイックソートのO(n log n)より遅いですが実装が単純です。
Q2. 配列[4,2,5,1,3]をバブルソートで昇順ソートした場合、1パス目終了後の配列はどれか。
✅ 正解は②。1パス目で最大値5が末尾に確定します。4↔2→[2,4,5,1,3]→4↔5なし→5↔1→[2,4,1,5,3]→5↔3→[2,4,1,3,5]。
Q3. バブルソートで2要素a[j]とa[j+1]を交換するとき、必要なものはどれか。
✅ 正解は②。一時変数tmpを使ってtmp←a[j]、a[j]←a[j+1]、a[j+1]←tmpの3ステップで交換します。tmpがないと値が上書きされてしまいます。
Q4. n個の要素をバブルソートで完全にソートするために必要なパス数は最大何回か。
✅ 正解は②。バブルソートはn-1パスで完了します。各パスで最大値が末尾に確定するため、n-1回のパスで全要素が確定します。例えばn=5なら4パスで完了。ただし早期終了の改良版では、スワップが1度もなかったパスでソート完了を検知できます。
Q5. バブルソートは「安定ソート」である。安定ソートとは何か。
✅ 正解は②。安定ソートとは、同じ値を持つ要素の元の順序がソート後も保たれるソートアルゴリズムのこと。バブルソートは隣の要素を比較して同じ値なら交換しないため安定ソートです。クイックソートは基本的には不安定ソートです。
Sponsor Link