バブルソートとは｜仕組み・計算量・最適化まとめ（初心者向け）

バブルソートとは

バブルソート（Bubble Sort）は最も基本的で教育的によく扱われる整列（ソート）アルゴリズムの一つです。隣接する要素を比較し、順序が逆であれば入れ替える（スワップする）操作を繰り返すことで配列全体を昇順または降順に整列します。名前は、比較的軽い（小さい）要素が泡のように配列の先頭に「浮き上がる」様子に由来します。

アルゴリズムの基本手順

最も単純な版の考え方は次の通りです。

• 配列の先頭から順に隣り合う要素を比較する。
• 順序が逆ならば入れ替える（スワップ）。
• 配列の末尾まで到達すると、最大（または最小）の要素が末尾に確定する。
• 末尾を除いた残りに対して同様のパスを繰り返す。

一般的な擬似コード（配列 A[0..n-1] を昇順にソート）:

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if A[j] > A[j+1]:
            swap A[j], A[j+1]

具体例（手順の追跡）

配列 [5, 2, 4, 3, 1] を昇順にバブルソートする一例（第1パス）：

• 比較(5,2) → 5>2 → swap → [2,5,4,3,1]
• 比較(5,4) → 5>4 → swap → [2,4,5,3,1]
• 比較(5,3) → swap → [2,4,3,5,1]
• 比較(5,1) → swap → [2,4,3,1,5]（最大値5が末尾に確定）

続けて残り部分に同様の処理を行い、最終的に [1,2,3,4,5] になります。

計算量（時間計算量とスワップ/比較の期待値）

バブルソートの時間計算量は一般に次のようにまとめられます。

• 最悪時（逆順など）: 比較回数は n(n-1)/2、スワップ回数も n(n-1)/2 に近く、O(n^2)
• 平均時（ランダムな順列）: 比較は Θ(n^2)、スワップ回数は期待値で n(n-1)/4（＝期待される逆順数）で Θ(n^2)
• 最良時（すでに整列済み、ただし簡易版では検出しない場合）: 比較は n(n-1)/2 のまま O(n^2)。ただし「早期打ち切り」を入れると O(n) になる。

メモリ使用量は定数オーダーで、追加領域は O(1)（インプレース）。

安定性・インプレース性

• 安定性: バブルソートは安定なソートです。等しいキーを持つ要素の相対順序を保ちます（隣接要素のみを交換するため）。
• インプレース: 追加の配列を必要とせず、定数領域のみで動作するためインプレースです。

最適化と変種

バブルソートにはいくつかの実用的な最適化や近い変種があります。

• 早期打ち切り（フラグ）: 内側ループで一度もスワップが発生しなければ配列は既に整列済みと判断して処理を終了できる。これにより最良時の計算量は O(n) になる。
• 境界縮小: 最後にスワップが発生した位置を記録して、その位置以降は次のパスで比較不要とすることで不要な比較を削減できる。
• コックテールソート（双方向バブル）: 通常の一方向パスの代わりに、往復（右へ→左へ）で走査する。これにより両端から「泡」を集められ、部分的に効果的に動作することがある。
• 奇偶トランスポジションソート（Odd-Even Transposition Sort）: 並列化に適した変種で、隣接ペア (0,1),(2,3)... と (1,2),(3,4)... を交互に比較交換する。並列計算モデルで有用。

性能・実用性の位置づけ（いつ使うべきか）

バブルソートは教育目的でアルゴリズムの基本概念（比較、スワップ、ループ、不変量など）を学ぶのに優れていますが、実用上はほとんど使われません。主な理由は O(n^2) の非効率性であり、以下のような代替アルゴリズムが実戦的には優れています。

• 挿入ソート（Insertion Sort）: 小規模データやほぼ整列済みデータで非常に高速で、定数因子も小さい。バブルよりも実際の性能が高いことが多い。
• 選択ソート（Selection Sort）: スワップ回数は少ないが比較回数は多い。安定性を持たせるには工夫が必要。
• クイックソート、マージソート、ヒープソート: 大規模データでは Θ(n log n) のアルゴリズムが推奨される。標準ライブラリもこれらのいずれかに基づくことが多い。

したがって、日常的なアプリケーションやライブラリ実装ではバブルソートは選択されません。ただし、講義や視覚化ツール、アルゴリズム入門の演習としては依然有用です。

理論的な観点（逆順数と交換回数の関係）

バブルソートにおける重要な理論的性質は「スワップ回数が配列の逆順（inversion）の数に等しい」点です。逆順とは i < j かつ A[i] > A[j] となるようなインデックス対の数です。逆順が減少することを単調量として扱えば、アルゴリズムが有限回で終了することや最悪ケースの下限を示すのに役立ちます。

実装上の注意点

• 比較にコストがかかる型（文字列や複雑な比較関数）の場合、比較回数削減の工夫（早期打ち切り、境界縮小）は重要。
• スワップコストが高い（大きな構造体をコピーするなど）場合は、ポインタや参照をスワップする、またはキーだけを交換してデータは別に保持するなどの工夫が有効。
• 言語やランタイムの最適化で、単純なループが非常に速くなることもあるが、アルゴリズムの漸近的格差（O(n^2) vs O(n log n)）は大きな差を生む。

教育的価値と視覚化

バブルソートは、ソート過程を視覚的に示すのに適しています。各パスで要素がどのように移動するか、隣接交換によってどのように逆順が減るかを直感的に理解できるため、アルゴリズム設計の基本を学ぶには良い題材です。また、コックテールソートや奇偶トランスポジションを合わせて比較することで並列性や局所性的な効果も示せます。

まとめ

バブルソートは実務での利用頻度は低いものの、アルゴリズム学習の導入として重要な位置を占めます。安定でインプレースなこと、逆順数との関係、早期打ち切りなどの最適化点を学べるため、教育用途や小規模・特殊ケースでは依然意味があります。大規模・一般的な用途では、挿入ソートやクイックソート、マージソートなどのより効率的なアルゴリズムを選択すべきです。

参考文献

• 「バブルソート」 - Wikipedia（日本語）
• Bubble sort - Wikipedia (English)
• Bubble Sort — GeeksforGeeks
• Algorithms, 4th Edition — Princeton University (Sedgewick & Wayne) — Elementary Sorts