バブルソートとは？エレベーターの入れ替えで理解するO(n²)

満員エレベーターを想像してほしい。

乗り込んだ人たちはバラバラの階に降りる。5階の人、1階の人、3階の人…。このとき「次オレ降りるから前行って」「いや私も次だから前行くわ」と、隣同士で場所を入れ替えながら降りる順番を整えていく。これがバブルソートだ。

「バブルソートは遅いから使わない」と教わった人は多い。それ自体は間違いではない。ただ、「なぜ遅いのか」を理解しないまま覚えても意味がない。エレベーターの入れ替えがなぜ非効率なのかを正確に理解することで、速いソートがなぜ速いのかが初めてわかる。

---

この記事でわかること

• バブルソートの動作をエレベーターの比喩で直感的に理解する
• 計算量O(n²)が「なぜそれだけ遅いのか」を数字で把握する
• フラグ最適化で最良ケースをO(n)に改善する方法
• 他のソートアルゴリズムとの比較と、バブルソートを学ぶ本当の理由

---

1パスで何が起きるか：一番「遠くに降りる人」が後ろへ移動する

📌 要点：隣り合う2要素を比較して大きい方を後ろへ動かす操作を1パスと呼ぶ。1パス終了ごとに未ソート部分の最大値が末尾に確定する。これを繰り返すことで全体がソートされる。

エレベーターに5人が乗っている。降りる階の番号でソートしたい。

[5階, 3階, 1階, 4階, 2階]

1周目（パス1）の動き：

比較する2人	状態	操作
5階 vs 3階	[5, 3, 1, 4, 2]	5>3なので入れ替え
5階 vs 1階	[3, 5, 1, 4, 2]	5>1なので入れ替え
5階 vs 4階	[3, 1, 5, 4, 2]	5>4なので入れ替え
5階 vs 2階	[3, 1, 4, 5, 2]	5>2なので入れ替え
1周終了	[3, 1, 4, 2, 5]	5階が最後尾に確定

1周するだけで、一番遠くに降りる「5階の人」が最後尾に収まった。5階の人は「次オレ降りるから前行って」と言いながら後ろへ後ろへと押されていったイメージだ。これが「泡が浮かび上がる」バブルの名前の由来でもある。

2周目、3周目と繰り返すと：

パス2終了: [1, 3, 2, 4, 5]  → 4階が確定
パス3終了: [1, 2, 3, 4, 5]  → 3階が確定
パス4終了: [1, 2, 3, 4, 5]  → すでに整列済み

n人いれば最大n-1周が必要になる。

Pythonで実装すると

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):           # パス数（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]  # 隣同士を入れ替え
    return arr

# 実行例
people = [5, 3, 1, 4, 2]
print(bubble_sort(people))  # → [1, 2, 3, 4, 5]

内側ループの n - 1 - i が重要だ。パスが進むたびに末尾の確定済みが増えるので、そこは比較しなくていい。

---

O(n²)の正体：入れ替え回数が爆発的に増える理由

📌 要点：n人でパスがn-1回、各パスの比較がn-1〜1回。合計n(n-1)/2回の比較が必要になりO(n²)となる。人数が2倍になると処理量は約4倍、10倍なら100倍になる。

バブルソートの計算量が O(n²) になる理由を、エレベーターで数えてみよう。

パス	比較回数
パス1（5人全員を比較）	4回
パス2（5階が確定済み）	3回
パス3	2回
パス4	1回
合計	10回 = n(n-1)/2

n=5なら10回。n=10なら45回。n=100なら4950回。n=1000なら499,500回。

人数が2倍になると、比較回数は約4倍になる——これがO(n²)の正体だ。

現実的なデータ量で考えると差は歴然だ。10万件のデータを並び替えるとき：

アルゴリズム	比較回数の目安
バブルソート O(n²)	約50億回
クイックソート O(n log n)	約170万回
差	約3000倍

エレベーターで全員が1人ずつ隣と入れ替わり続けるのは、人数が増えれば増えるほど非現実的になっていく。

---

フラグで賢くする：「もう整列済みならすぐ終わろう」

📌 要点：1パスで一度も入れ替えが起きなければ配列はソート済み。フラグで検出して即終了することで、整列済みデータへの処理をO(n²)からO(n)に改善できる。

基本実装のバブルソートには致命的な無駄がある。すでに整列が終わっていても、n-1パスを全部実行してしまうのだ。

エレベーターで言えば「全員もうちゃんと並んでいる」のに「念のためもう1周入れ替えチェックします」をやり続けるようなものだ。

フラグを1行加えるだけで解決できる。

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False               # 「今周は入れ替えなかった」フラグ
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True        # 入れ替えが起きたのでフラグを立てる
        if not swapped:
            break                     # 1周入れ替えゼロ → もう整列済み → 即終了
    return arr

この最適化の効果：

ケース	最適化前	最適化後
最良（整列済み）	O(n²)	O(n) ← 劇的改善
平均	O(n²)	O(n²)
最悪（完全逆順）	O(n²)	O(n²)

「ほぼ整列済みのデータ」を繰り返し処理するような場面では、フラグ版が大幅に速くなることがある。実装コストはフラグ1行だけなので、使わない理由がない。

---

他のソートと比べると：エレベーターの限界を知る

📌 要点：バブルソートは実用では使われないが、比較基準として価値がある。「安定ソートかどうか」はソート後の順序保持が重要な業務データ処理で意識すべき性質。

アルゴリズム	最良	平均	最悪	安定性	一言で言うと
バブルソート	O(n)	O(n²)	O(n²)	✅ 安定	最も直感的、最も遅い
選択ソート	O(n²)	O(n²)	O(n²)	❌ 不安定	交換回数は最小
挿入ソート	O(n)	O(n²)	O(n²)	✅ 安定	ほぼ整列済みに強い
マージソート	O(n log n)	O(n log n)	O(n log n)	✅ 安定	安定かつ大規模対応
クイックソート	O(n log n)	O(n log n)	O(n²)	❌ 不安定	実用で最もよく使われる

「安定性」とは、同じ値を持つ要素の元の順序が入れ替わらない性質だ。たとえば社員を「給与順」にソートしたとき、同じ給与の社員が元の並び順を保つかどうかを指す。

情シス部門の実務で言うと、Pythonの sorted() が採用している Timsort は安定ソートだ。挿入ソートとマージソートを組み合わせた設計で、ほぼ整列済みのデータに対して特に速く動く。業務でPythonを使う限り、自前でバブルソートを実装する機会はまずない。

それでもバブルソートを学ぶ価値はある。「なぜ遅いか」を言語化できない人が、「なぜ速いか」を理解できるわけがないからだ。

---

FAQ

---

まとめ

• バブルソートは隣同士が「前行って」と入れ替わり続けるエレベーターそのもの
• 計算量はO(n²)。人数が2倍になると処理量は約4倍になる
• フラグ1行追加するだけで、整列済みデータへの処理をO(n²)→O(n)に改善できる
• 実用では Timsort（Pythonのsorted）やクイックソートが主役。バブルソートは学習用途が中心
• 「なぜ遅いか」を正確に言えること——それが速いアルゴリズムを理解するための土台になる

エレベーターで全員が1人ずつ隣と確認し合いながら並び直すのは、人数が少なければ合理的だ。でも100人で同じことをやったら乗り降りする前にドアが閉まってしまう。問題の規模に対して何が「合理的」かを判断する視点を持てるようになることが、この記事の本当のゴールだ。

---

関連記事

ソートの速さが「なぜ違うのか」を計算量から理解したい方はこちら。
→ アルゴリズムのオーダー記法をマンガで理解する

「分割して速くする」クイックソートの思想に進みたい方はこちら。
→ クイックソートとデカルトの分割統治
“`