Overview
Bubble Sort は隣り合う要素を比較し、順序が逆なら swap します。各 pass で最大の未確定要素が右端へ移動します。
Analogy
水中の泡が上に上がるように、大きい値が毎ラウンド右側へ押し上げられます。
Step-by-step
- 配列を走査して arr[j] と arr[j+1] を比較する。
- arr[j] > arr[j+1] なら swap する。
- 1 回の pass 後に最大要素が末尾へ確定する。
- 末尾は sorted なので次の pass の範囲を縮める。
- swap が 0 回なら早期終了する。
Visual
Pass 1: [5,3,8,1,2] -> [3,5,1,2,8]。その後は確認範囲が段階的に小さくなる。
Common mistakes
- inner loop の境界を縮めない。
- >= を使って stability を壊す。
- swap なしの pass で break しない。
Practice questions
- すでに sorted な入力で early exit あり/なしの比較回数を数える。
- Bubble Sort が stable な理由を説明する。
- descending に並べるよう条件を変更する。
Time
O(n²) worst/average, O(n) best with early exit