バブルソート解説 — ステップごとの動作

バブルソートの動作原理

バブルソートは最もシンプルな比較ベースのソートアルゴリズムです。配列を繰り返し走査し、隣接する要素のペアを比較して、順序が間違っていればスワップします。スワップが不要になるまでこのプロセスを繰り返し、配列がソートされます。

アルゴリズムのステップ

for i = 0 to n-2:
  for j = 0 to n-2-i:
    if arr[j] > arr[j+1]:
      swap(arr[j], arr[j+1])

配列を完全に1回走査するたびに、未ソートの最大の要素が正しい位置まで「浮かび上がる」ことから、この名前が付けられました。

パスごとの例

配列 [5, 3, 8, 1, 2] を考えます：

• パス1: (5,3)比較→スワップ → (3,8)→スワップなし → (8,1)→スワップ → (8,2)→スワップ → [3, 5, 1, 2, 8]
• パス2: (3,5)→なし → (5,1)→スワップ → (5,2)→スワップ → [3, 1, 2, 5, 8]
• パス3: (3,1)→スワップ → (3,2)→スワップ → [1, 2, 3, 5, 8]
• パス4: スワップなし → 配列はソート済み

時間計算量分析

ケース	計算量	条件
最良	O(n)	配列がすでにソート済み（早期終了あり）
平均	O(n²)	ランダムな順序
最悪	O(n²)	逆順にソート

早期終了の最適化

重要な最適化は、パス中にスワップが発生したかどうかを追跡することです。完全なパスでスワップがゼロの場合、配列はすでにソートされており、アルゴリズムは早期に終了できます。この最適化により、ソート済み入力に対する最良ケースはO(n)になります。

空間計算量

バブルソートはスワップ用の一時変数のみ必要なため、O(1)の追加空間を使用します。インプレースかつ安定なソートアルゴリズムであり、等しい要素は元の相対順序を維持します。