バブルソート

隣同士の値を比較し、順序が逆なら交換します。大きい値が右へ移動し、末尾で確定します。

再生するか、1ステップずつ進めてください。スライダーで位置を移動できます。「ほぼ整列済み」では早期終了を確認できます。

最良O(n)

平均O(n²)

最悪O(n²)

追加領域O(1)

安定はい

最大比較回数n(n−1)/2

1周ごとに最大値が1つ確定する

各比較で大きい方が右へ移るため、1周すると区間の最大値が末尾に到達します。次の周では確定位置を除外します。1周の間に交換がなければ整列済みなので終了します。整列済みの入力ではO(n)です。

演習：交換回数と転倒数

転倒とはi < jかつa[i] > a[j]となる組です。バブルソートの1回の交換は転倒をちょうど1つ解消するため、交換回数は転倒数と等しくなります。大きなnではマージソートを用いてO(n log n)で数える方法が適しています。