バブルソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

最初の2要素を比較し、前のほうが大きければ交換します。次に2番目と3番目、3番目と4番目と、リストの末尾まで続けます。これが1パスです。1回目のパスの後、すべての比較で大きい値が1つ右に運ばれるため、最大の要素は必ず末尾にあります。

未ソートの部分に対してパスを繰り返します。この部分は毎回1要素ずつ小さくなります。1回のパスで交換がまったく起こらなければ、リストはソート済みなので、そこで早期に終了できます。

具体例をパスごとに見る

[5, 1, 4, 2, 8] を昇順にソートします。バーの後ろの要素は最終位置に収まっています。

早期終了がなければ、アルゴリズムは4回目のパスを実行します。早期終了があれば、この例では3パスで十分です。

Pythonでの実装

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

内側のループは、end より後ろがすでに確定しているため、end で止まります。swapped フラグによって、ソート済みの入力では最良ケースの O(n) になります。

時間計算量と空間計算量

逆順の1万要素では、ほぼ5,000万回の比較と交換になります。交換の回数は常に転倒数（順序が逆になっている要素のペアの数）と等しくなります。

バブルソートと他のソートの比較

バブルソートが安定なのは、隣り合う要素だけを、しかも厳密に逆順のときだけ交換するため、等しい要素が互いを追い越さないからです。挿入ソートも同じ計算量と安定性を持ちますが、実際には書き込み回数が少なく高速なので、Timsort のようなハイブリッドアルゴリズムの内部で使われるのは、バブルソートではなく挿入ソートです。

派生と、よくある間違い

• シェーカーソート（カクテルソート）は、パスごとに左から右、右から左と交互に進み、末尾にある小さな要素（「亀」と呼ばれます）を先頭へ速く運びます。それでも O(n²) です。
• コムソートは、一定の間隔だけ離れた要素を比較し、その間隔を縮めていくことで、多くの亀を早い段階で取り除きます。間隔が 1 になるとバブルソートそのものになります。
• 奇偶転置ソートは、奇数番目のペアをすべて比較し、次に偶数番目のペアをすべて比較する方法で、並列ソートの教材として使われます。

バブルソートを使う場面

本番コードでは、ほとんど使いません。Pythonでは sorted(items) か items.sort() を呼びます。これらは Timsort を使い、O(n log n) で動作し、安定です。それでもバブルソートを知っておく価値があるのは、最も説明しやすいソートであり、正しさの証明も追いやすく、ループ・交換・計算量に関する面接や試験の最初の定番問題だからです。

唯一の実用上の利点は、ソート済みのリストを O(n) の1パスで検出できることですが、隣同士を比べる単純なループなら、何もソートせずに同じことができます。