女性向けエンジニアスクール
3秒でわかる
隣り合う二つを比べて順序が逆なら入れ替える並べ替えの手法。速くはないものの動きが追いやすく、計算量を学ぶ入口になります。
もう少し詳しく
どういうものか
バブルソートは、隣り合う二つの要素を比べ、順序が逆であれば入れ替える操作を端から端まで繰り返す並べ替えの手法になる。一周すると最大の値が右端まで移動し、次の周では残りの範囲について同じことを行う。大きな値が泡のように浮き上がっていく様子から、この名前が付いている。
なぜ必要か
実務でバブルソートを書く場面はほとんどない。標準ライブラリの並べ替えのほうが速いためで、それでも学ぶ理由は、計算量の考え方を最初に体感できる題材だからになる。要素が n 個のとき比較回数はおよそ n の 2 乗に比例し、要素が 10 倍になれば時間は 100 倍になる。この感覚を持っているかどうかが、後で扱うマージソートやクイックソートの利点を理解できるかを分ける。
具体例
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 一度も交換が無ければ<a href="/glossary/alignment" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">整列</a>済み
break
return a
print(bubble_sort([5, 3, 8, 1])) # [1, 3, 5, 8]途中経過は次のように進む。
開始 5 3 8 1
1周目 3 5 1 8 (8 が右端へ確定)
2周目 3 1 5 8 (5 が確定)
3周目 1 3 5 8 (完成)
