Bubble Sortとは

Bubble Sort（バブルソート）とは、隣り合う要素を比較し交換することを繰り返してソートするアルゴリズム。安定なソートの一種。

アルゴリズム

1. 先頭から隣り合う要素を2つずつ比較し、先頭側が小さくなるように入れ替える
2. 末尾まで行ったら、見る範囲の終端を1つ先頭側へずらして¹、再度先頭から隣り合う要素を2つずつ比較し、先頭側が小さくなるように入れ替える
3. これを比較ができなくなるまで続ける
   • 見る範囲の終端が先頭に達したら終了

一度もスワップが発生しなかった場合に、ソートが完了していると判断して終了するようにすると、計算量を多少改善できる。

実装例

def bubble_sort(numbers: list[int]) -> list[int]:
    for limit_idx in range(len(numbers), 1, -1):
        for i in range(1, limit_idx):
            if numbers[i - 1] > numbers[i]:
                numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
    return numbers

計算量

要素数を$n$とする。

Pros

• アルゴリズムがシンプル
• 実装が簡単
• 安定なソート
• メモリ使用量が少ない

Cons

• 効率が悪い
• 計算量が大きいため速度は遅い
• ほとんどの場合、他のソートアルゴリズムの方が良い

利用場面

• 要素数が少ない場合 : シンプルさと容易さが有利になることがある
• 教育目的 : アルゴリズムの理解を深めるために用いられることがある
• ほぼソートされているデータ : 他のソートアルゴリズムよりも速いことがある