Bubble Sort（バブルソート）とは、隣り合う要素を比較し交換することを繰り返してソートするアルゴリズム。安定なソートの一種。
- 先頭から隣り合う要素を2つずつ比較し、先頭側が小さくなるように入れ替える
- 末尾まで行ったら、見る範囲の終端を1つ先頭側へずらして1、再度先頭から隣り合う要素を2つずつ比較し、先頭側が小さくなるように入れ替える
- これを比較ができなくなるまで続ける
- 見る範囲の終端が先頭に達したら終了
一度もスワップが発生しなかった場合に、ソートが完了していると判断して終了するようにすると、計算量を多少改善できる。
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$とする。
| 計算量 | |
|---|---|
| Average | $\mathrm{O}(n^2)$ |
| Best | $\mathrm{O}(n)$ |
| Worst | $\mathrm{O}(n^2)$ |
- アルゴリズムがシンプル
- 実装が簡単
- 安定なソート
- メモリ使用量が少ない
- 効率が悪い
- 計算量が大きいため速度は遅い
- ほとんどの場合、他のソートアルゴリズムの方が良い
- 要素数が少ない場合 : シンプルさと容易さが有利になることがある
- 教育目的 : アルゴリズムの理解を深めるために用いられることがある
- ほぼソートされているデータ : 他のソートアルゴリズムよりも速いことがある
末尾まで行った時点で、末尾には必ず最大値が格納されるため。 ↩︎