バブルソート — Project Hematite

バブルソートはほとんどのプログラマが最初に出会い、最も早く引退させるアルゴリズムだ。大きな入力に対しては遅いが、その構造は数行で正しさを証明できるほどシンプルで、すでにソートされたデータに対しては $O(n)$ 時間で終了する — これは選択ソートより良い。

アルゴリズム

配列を走査する各パス（pass）は、隣接するすべてのペアを比較し、逆順であれば 2 つをスワップする。1 回の完全なパスの後、最大要素が最後の位置に「浮かび上がる」（bubble）。2 回のパスの後、2 番目に大きい要素が定位置に収まる。 $n-1$ 回のパスの後、配列はソートされる。

fn bubbleSortNaive(arr: []i64) void {
    var pass: usize = 0;
    while (pass < arr.len) : (pass += 1) {
        var i: usize = 1;
        while (i < arr.len - pass) : (i += 1) {
            if (arr[i - 1] > arr[i]) {
                const tmp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

早期終了最適化

1 回の完全なパスでスワップが発生しなければ、配列はすでにソートされているのでアルゴリズムは停止できる。さらに、パス内の最後のスワップ位置より後ろの要素はすでに最終位置に収まっている — そのため常に 1 つずつ縮小するのではなく、その位置まで未ソート領域を縮小できる。

fn bubbleSort(arr: []i64) void {
    var n = arr.len;
    while (n > 1) {
        var last_swap: usize = 0; // このパスの最後のスワップ位置
        var i: usize = 1;
        while (i < n) : (i += 1) {
            if (arr[i - 1] > arr[i]) {
                const tmp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = tmp;
                last_swap = i;
            }
        }
        n = last_swap; // インデックス ≥ last_swap の要素はソート済み
    }
}

last_swap がパス全体で 0 のままだった場合（スワップなし）、n が 0 になって外側のループはすぐに終了する。これが早期終了条件だ。

ループ不変条件による正しさの証明

不変条件：各パスの開始時に、arr[n..] は $(\text{arr.len} - n)$ 個の最大要素をソート済みかつ最終位置に保持している。

最初のパス前：n = arr.len なので arr[n..] は空 — 空虚に真だ。
維持：内側のループは arr[0..n] のすべての隣接ペアを比較する。各スワップで大きい値が 1 ステップ右に移動する。i が n-1 に達するまでに、arr[0..n] の最大要素が位置 n-1 に浮かび上がる。n = last_swap を設定すること（旧 n 以下）は未ソート領域を縮小するだけで、不変条件は次のパスに対して再確立される。
終了：n は各パスで厳密に減少する（last_swap < n に移動するか、スワップなしで 0 になる）。最終的に n ≤ 1 となり、これは自明にソート済みだ。

ループが終了するとき、不変条件は配列全体がソート済みであることを保証する。

安定性

バブルソートは安定（stable）だ：2 つの要素が等しいとき、arr[i - 1] > arr[i] の条件が偽になるためスワップされない。等しい要素は元の相対順序を保つ。

計算量

ケース	比較回数	スワップ回数
最良（ソート済み）	$O(n)$	$0$
最悪（逆ソート）	$\Theta(n^2)$	$\Theta(n^2)$
平均	$\Theta(n^2)$	$\Theta(n^2)$

最良ケースは早期終了最適化で $O(n)$ だ：1 回のパスでスワップがなければ $n-1$ 回の比較の後にループが終了する。

最悪ケースは逆ソートされた入力だ。各要素は配列の端から端まで浮かび上がる必要がある：位置 $k$ の要素には $k$ 回のスワップが必要で、合計 $\sum_{k=0}^{n-1} k = \frac{n(n-1)}{2} = \Theta(n^2)$ 回のスワップと比較になる。

空間計算量は $O(1)$ — 入力配列に加えてスワップ用の変数 1 つだけが必要だ。

バブルソートが実用されない理由

このシリーズの 3 つの二乗ソート（バブル、選択、挿入）はすべて $O(n^2)$ の最悪ケースを持つ。挿入ソートは実用的にはバブルソートより明らかに優れている：書き込み回数が少なく、内側のループは正しい位置が見つかり次第終了し、定数倍も小さい。バブルソートの選択ソートに対する唯一の優位点は、早期終了によって真の $O(n)$ の最良ケースを持つことだ。

数百要素を超えるあらゆる $n$ に対しては、マージソートまたはクイックソートを使う。

まとめ

バブルソートは隣接するペアを比較して逆順であればスワップし、完全なパスでスワップがなくなるまで繰り返す。
各パスの後、最大の未ソート要素が最終位置に収まる。
早期終了最適化は未ソート領域を最後のスワップ位置まで縮小し、ソート済み入力に対して $O(n)$ 時間を実現する。
最悪ケースと平均ケースの時間は $\Theta(n^2)$ 、空間は $O(1)$ だ。
バブルソートは安定だ：等しい要素はスワップされない。
単純な $O(n^2)$ アルゴリズムの実用的な使用には、バブルソートより挿入ソートを選ぶ。