Pythonのバブルソートとは？仕組みと実装例をわかりやすく解説

バブルソート（Bubble Sort）は、リストを昇順（または降順）に並べ替えるためのソートアルゴリズムです。仕組みが非常にシンプルで初心者にも理解しやすい一方、処理効率はあまり高くありません。小規模なデータには使えますが、要素数の多いリストや配列では時間がかかります。時間計算量は O(n²) です。

ただし、バブルソートは「インプレース（in-place）」型のアルゴリズムであり、並べ替えに追加のメモリ領域をほとんど必要としません。そのため、空間計算量の面では効率的です。とはいえ、クイックソートやマージソートなど、より高速なアルゴリズムが存在するため、実務でバブルソートが使われることは少ないのが実情です。

バブルソートの仕組み

バブルソートでは、2つのforループを使用します。外側のループはリスト全体を反復し、内側のループも外側の各反復ごとにリストを走査します。

バブルソートの中心となる操作は、隣り合う2つの要素の比較です。前の要素が次の要素より大きければ両者を入れ替え、小さい要素を前に、大きい要素を後ろへ移動させます。

外側のループの1回目の反復が終わると、リスト内の最大値が末尾のインデックスに確定します。2回目の反復では2番目に大きい値が後ろから2番目へ、という具合に、大きい値が泡のように浮かび上がっていくことから「バブル（泡）ソート」と呼ばれます。すべての反復が完了すると、ソート済みのリストが完成します。

それでは、具体例で確認してみましょう。

例：次のリストを昇順に並べ替える

外側のループ 1回目

5＞2 なので、両者を入れ替えます。

5＞1 なので、両者を入れ替えます。

5＞3 なので、両者を入れ替えます。

5＞4 なので、両者を入れ替えます。

（1回目の外側の反復が終了し、最大値の5が末尾のインデックスに確定しました）

外側のループ 2回目

2＞1 なので、入れ替えます。

2＜3 なので、入れ替えは不要です。

3＜4 なので、入れ替えは不要です。

ご覧のとおり、リストは2回目の外側の反復の時点ですでにソート済みになっています。しかし、基本実装では外側のループは残りの反復も入れ替えなしで走査し続けます。ここでは説明のため2回分のみを示しました。リストの初期状態によっては最初の反復で完了することもあれば、最後の反復までかかることもあり、外側のループは常に n 回反復するのが基本です。

Pythonでの実装例

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

array = [2, 3, 1, 5, 4]
print(bubble_sort(array))

出力結果

[1, 2, 3, 4, 5]

補足：早期終了による最適化

ある反復で一度も入れ替えが発生しなければ、リストはすでにソート済みだと判断できます。この性質を利用してフラグを導入すると、不要な反復を打ち切ることができ、整列済みの入力に対しては最良計算量が O(n) まで改善されます。さらに、内側のループの範囲を n-1-i にすれば、すでに確定した末尾部分の再比較を避けられます。

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        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
    return arr

print(bubble_sort_optimized([2, 3, 1, 5, 4]))
# [1, 2, 3, 4, 5]