バブルソートは、隣接する要素を比較しながら順番を入れ替えることで、リストをソートする単純なアルゴリズムです。
リストの中で隣り合う要素を比較し、大きい（または小さい）方を後ろに押し出していくため、大きい値（または小さい値）が「泡（bubble）」のようにリストの端に浮かび上がるように見えることからこの名前がついています。
- リストの先頭から順に隣接する2つの要素を比較する。
- 大小関係が正しくない場合は交換する。
- リストの末尾までこの操作を繰り返すと、最も大きい（または小さい）要素がリストの最後に移動する。
- 未ソート部分を減らし、再び 1 から繰り返す。
- すべての要素が正しい順番になるまで続ける。
BubbleSort(A, n)
for i = 0 to n-1 do
for j = 0 to n-1-i do
if A[j] > A[j+1] then
swap(A[j], A[j+1])
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i): # 末尾のソート済み部分は除外
if arr[j] > arr[j + 1]: # 隣り合う要素を比較
arr[j], arr[j + 1] = arr[j + 1], arr[j] # 交換
swapped = True
if not swapped: # 交換がなかったら終了（最適化）
break
return arr
# 実行例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print(sorted_arr) # [11, 12, 22, 25, 34, 64, 90]この実装では、swapped フラグを導入して、交換が一度も行われなければソート完了とみなして途中でループを抜ける最適化を行っています。
| ケース | 計算量 |
|---|---|
| 最悪ケース | (O(n^2)) |
| 平均ケース | (O(n^2)) |
| 最良ケース（すでにソート済み） | (O(n)) |
- 最悪ケース: 逆順ソートされている場合、すべての要素を比較・交換するため、計算量は (O(n^2)) になります。
- 最良ケース: すでにソート済みの場合、1回目のループで
swapped = Falseとなり、早期終了できるため (O(n)) となります。
✅ 実装が簡単（初心者でも理解しやすい）
✅ 追加のメモリをほとんど使わない（in-placeソート）
❌ 処理が遅い（効率が悪く、実用性が低い）
❌ 大量のデータには向かない（他のソートアルゴリズムよりも遅い）
| ソートアルゴリズム | 最悪時間計算量 | 最良時間計算量 | 平均時間計算量 | 安定性 | 追加メモリ |
|---|---|---|---|---|---|
| バブルソート | (O(n^2)) | (O(n)) | (O(n^2)) | ✅ | (O(1)) |
| 選択ソート | (O(n^2)) | (O(n^2)) | (O(n^2)) | ❌ | (O(1)) |
| 挿入ソート | (O(n^2)) | (O(n)) | (O(n^2)) | ✅ | (O(1)) |
| クイックソート | (O(n^2)) | (O(n \log n)) | (O(n \log n)) | ❌ | (O(\log n)) |
| マージソート | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | ✅ | (O(n)) |
✅ 学習目的: アルゴリズムの基本を学ぶには良い
✅ 小規模なデータ: 10個程度の要素なら問題なく動作
❌ 大規模データ: 1000個以上のデータでは非常に遅いので不向き
❌ 実用システム: 実際のアプリケーションではほぼ使われない
バブルソートは改良できます。
例えば、"どこまでソートが済んだかを記録" することで、不要な比較を減らす方法があります。
def optimized_bubble_sort(arr):
n = len(arr)
last_swap = n - 1
while last_swap > 0:
new_swap = 0
for i in range(last_swap):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
new_swap = i
last_swap = new_swap # 交換が発生した最後の位置まででソート
return arrこの方法では、ソート済みの部分をスキップ できるため、少し高速化できます。
- バブルソートは シンプルなソートアルゴリズム だが、計算量が (O(n^2)) と遅い ため、大きなデータには向かない。
- 最適化（交換フラグや最終交換位置の記録）により 無駄な比較を減らせる。
- 学習目的 には最適だが、実際のアプリケーションでは クイックソートやマージソートを使う のが一般的。