隣接する2要素を比較して大きい値を後ろへ送るバブルソートを棒アニメーションで確認。比較・交換カウンタと疑似コードハイライトでO(n²)の遅さを実感できます。
アルゴリズム
配列
比較
0
交換/書込
0
ステップ
0/1,722
読み
0
補助メモリ
0
再帰の深さ
1/1
速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。
疑似コード
for i ← 0 to n−1
for j ← 0 to n−i−2
if a[j] > a[j+1]
swap a[j] ↔ a[j+1]
// a[n−1−i] 확정
計算量
| 最良 | O(n) |
|---|---|
| 平均 | O(n²) |
| 最悪 | O(n²) |
| 空間 | O(1) |
| 安定 | ○ |
バブルソートは配列の先頭から隣接2要素を比較し、左が大きければ交換を繰り返すアルゴリズムです。1パスごとに最大値が「泡」のように末尾へ浮き上がるのが名前の由来です。
比較は約n²/2回で平均O(n²)ですが、交換なしで1パスが終われば早期終了でき最良O(n)になります。同値の順序が保たれる安定ソートです。 ソート可視化