選択ソート — Project Hematite

ソートアルゴリズムにおける各スワップはメモリへの書き込みだ。バブルソートは最悪ケースで $\Theta(n^2)$ 回のスワップを行うことがある。選択ソートはそれを最大 $n - 1$ 回 — 入力に関わらず 1 パスにつき 1 回 — に抑える。書き込みが高価な場合（フラッシュストレージなど）、これが重要になる。

アルゴリズム

選択ソートは配列をソート済み前半部分と未ソート後半部分に分ける。各パスで未ソート後半部分の最小値をスキャンし、その最小値を未ソート後半部分の最初の位置にスワップして、ソート済み前半部分を 1 つ拡張する。

fn selectionSort(arr: []i64) void {
    var i: usize = 0;
    while (i < arr.len) : (i += 1) {
        // arr[i..] の最小値のインデックスを見つける
        var min_idx = i;
        var j = i + 1;
        while (j < arr.len) : (j += 1) {
            if (arr[j] < arr[min_idx]) min_idx = j;
        }
        // 最小値を位置 i にスワップ
        if (min_idx != i) {
            const tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

if (min_idx != i) のガードは、最小値がすでに位置 i にある場合のムダなスワップを避ける。

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

不変条件：反復 $i$ の開始時に、arr[0..i] は元の配列の $i$ 個の最小要素をソート順で格納しており、それぞれが最終位置にある。

反復 0 の前：arr[0..0] は空 — 空虚に真だ。
維持：内側のループが arr[i..] の最小値のインデックス min_idx を見つける。スワップの後、arr[i] がその最小値を保持する。arr[0..i] はすでに $i$ 個の最小要素を含んでいたので、arr[i] は $(i+1)$ 番目に小さい要素だ。前半部分 arr[0..i+1] はソートされており各要素は最終位置にある。
終了： $i$ は各反復で 1 増加する。 $i = \text{arr.len} - 1$ のとき、後半部分には要素が 1 つだけ残り、前半部分の不変条件によりそれはすでに正しい位置にある。

ループが終了するとき、arr[0..arr.len] は配列全体がソート順になる。

選択ソートが安定でない理由

安定性（stability）は等しい要素が元の相対順序を保つことを意味する。選択ソートは安定でない：最小値を探すスワップは等しい隣接要素を超えて要素を移動させることがある。

[5, 5*, 2] を考えよう（5* は 2 番目の 5 のコピーで識別のため星印をつけた）。

パス 0：最小値はインデックス 2 の 2。arr[0] と arr[2] をスワップ：[2, 5*, 5]。

元の最初の 5 は今 5* の右にあり、順序が逆転した。これは安定性に違反する。

計算量

比較回数

内側のループは $i = 0$ に対して $n - 1$ 回、 $i = 1$ に対して $n - 2$ 回、 $i = n - 2$ に対して $1$ 回実行される：

(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = \Theta(n^2).

この回数は入力がどんなものでも同じ — ソート済みでも逆ソートでもランダムでも — なぜならアルゴリズムは常に完全な未ソート後半部分をスキャンするからだ。選択ソートには最良ケースがない。

スワップ回数

最大 $n - 1$ 回のスワップ（1 パスにつき 1 回、最小値がすでに定位置にある場合はスキップ）。これは $O(n)$ で、バブルソートの最悪ケース $\Theta(n^2)$ よりはるかに少ない。

空間

$O(1)$ の余分な空間 — 入力配列に加えてインデックス変数のみ。

指標	計算量
比較回数	常に $\Theta(n^2)$
スワップ回数	$O(n)$
余分な空間	$O(1)$
安定	いいえ

選択ソートが優位な場面

書き込みが高価なメディア：各スワップが高価な場合（SSDの消耗、リモート書き込み）、比較回数が少ないアルゴリズムでも $O(n^2)$ の書き込みを行うより $O(n)$ スワップが有利なことがある。
非常に小さい配列： $n \le 5$ では、より洗練されたアルゴリズムのオーバーヘッドは割に合わない。

より大きな入力には、挿入ソートがより良いインプレース $O(n^2)$ の選択であり、マージソートまたはクイックソートが $O(n \log n)$ を与える。

まとめ

選択ソートは未ソート後半部分の最小値を見つけてその先頭にスワップし、ソート済み前半部分を拡張する。
ループ不変条件が正しさを保証する： $i$ 回のパスの後、 $i$ 個の最小要素が最終位置に収まる。
比較回数は常に $\Theta(n^2)$ — 入力の順序は関係ない。
スワップ回数は最大 $O(n)$ で、これがアルゴリズムの主な実用的優位点だ。
選択ソートは安定でない：最小値のスワップが等しい要素の相対順序を変えることがある。