Pythonのバブルソート(bubble sort)
このレッスンでは、バブルソートを実装し、リストが並べ替え済みになったら早めに終える工夫を加えます。
はじめに
どんな問題を解決するか
並べ替えはどこにでもあり、その仕組みを理解すると速さについて考えられるようになります。バブルソートは1ステップずつ追いかけやすい最も簡単な並べ替えアルゴリズムなので、実際のプログラムではもっと速い方法を使うものの、最初の例としてよく使われます。
身近なたとえ
バブルソートは、隣り合う2人を入れ替えることだけで子どもたちを背の順に並べるようなものです。列に沿って歩き、背の高い子が前にいるペアを入れ替えます。1回歩くと、いちばん背の高い子は水面に浮かぶ泡のように列の最後に着きます。入れ替えが1回も起きなくなるまで繰り返します。
result[index] > result[index + 1]👫 背の高い子が前にいる?result[index], result[index + 1] = ...🔄 隣の2人を入れ替えるfor end in range(len(result) - 1, 0, -1):🚶 毎回1人短くして、もう一度列を歩くif not swapped: break✅ 1回も入れ替えがなければ並べ終わりバブルソートはリストを何度も通り、順番が間違っている隣り合う要素を入れ替え、1回通っても入れ替えがなくなったら終わります。一般に O(n²) の時間がかかります。
重要なポイント
result = values.copy()はコピーを並べ替えるので、呼び出し元のリストは変わりません。if result[index] > result[index + 1]:は順番が間違っているペアを入れ替えます。- 最大の値はすでに最後にあるので、
endは1回ごとに短くなります。 if not swapped: breakは入れ替えがなければ早めに止まるので、並べ替え済みのデータは1回で終わります。
どんな場面で使う?
- 比較による並べ替えの仕組みを学ぶ。
- 教材や可視化で使うごく小さなリスト。
- リストがすでに並べ替え済みかを1回で確かめる。
使わなくてよいとき
- 実際のプログラム:
sorted()とlist.sort()のほうがはるかに速く(O(n log n))、テストもされています。 - 数百を超える要素のリスト:比較の回数が長さの2乗で増えます。
Pythonのバブルソート(bubble sort)のビジュアライザー
O(n²)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
実行結果
[1, 2, 4, 5, 8]
コードの解説
1回の走査が終わるたびに、未整列部分の最大値が最後の正しい位置に収まるので、次の走査は1要素ぶん短くなります。変数swappedはその走査で入れ替えがあったかを記録します。入れ替えが1回もなければリストはすでに並んでいるので、ループを早めに終えます。最悪の計算量はO(n²)なので、大量のデータには向きません。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
1つ先まで行きすぎる
index が最後の位置に来ると result[index + 1] が範囲外になります。
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ