バブルソート - データサイエンス関連+αのメモ

バブルソート（bubble sort） は隣り合う要素を比較して、順序が逆なら交換する操作を繰り返すソートアルゴリズム。大きな値が泡（バブル）のように末尾へ浮き上がっていく様子からこの名がある。

	計算量
最悪時間計算量	$O(n^2)$
平均時間計算量	$O(n^2)$
最良時間計算量	$O(n)$ （改良版、既ソート済み）
空間計算量	$O(1)$ （in-place）

特徴

安定ソート（同じ値の要素の相対順序が保たれる）
in-place（追加メモリが不要）
実用上は遅いが、実装がシンプル

アルゴリズム¶

配列の先頭から隣接する2要素を比較し、逆順なら交換する
1パス（pass, イテレーション）終わると最大値が末尾に確定する
確定した末尾を除いて同じ操作を繰り返す
交換が1度も起きなければ完了（早期終了）

def bubble_sort(arr: list) -> list:
    a = arr.copy()
    n = len(a)
    for n_pass in range(n):
        swapped = False
        for i in range(n - 1 - n_pass):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i] # 交換
                swapped = True
        if not swapped:  # 交換なし → ソート済み
            break
    return a

import random

data = [64, 34, 25, 12, 22, 11, 90]
print("入力:", data)
print("出力:", bubble_sort(data))

# ランダムデータで検証
random.seed(42)
large = random.sample(range(1000), 20)
assert bubble_sort(large) == sorted(large)
print("ランダム20件: OK")

入力: [64, 34, 25, 12, 22, 11, 90]
出力: [11, 12, 22, 25, 34, 64, 90]
ランダム20件: OK

ステップ可視化¶

def bubble_sort_verbose(arr: list) -> list:
    a = arr.copy()
    n = len(a)
    for n_pass in range(n):
        swapped = False
        for i in range(n - 1 - n_pass):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i] # 交換
                swapped = True
        print(f"パス {n_pass + 1}: {a}")
        if not swapped:  # 交換なし → ソート済み
            break
    return a

data = [5, 3, 8, 1, 4]
print("入力:", data)
bubble_sort_verbose(data)

入力: [5, 3, 8, 1, 4]
パス 1: [3, 5, 1, 4, 8]
パス 2: [3, 1, 4, 5, 8]
パス 3: [1, 3, 4, 5, 8]
パス 4: [1, 3, 4, 5, 8]

[1, 3, 4, 5, 8]