選択ソート

選択ソートは未整列部分の最小値を探し、その先頭と交換するアルゴリズムです。時間計算量は最良・平均・最悪とも O(n²)、追加空間は O(1) です。交換は各走査で最大1回、合計でも n − 1 回以下です。

全員の身長を調べ、最も低い人を列の先頭へ移す操作に似ています。探すための比較は何度も行いますが、移すのは選ばれた1人だけです。

選択ソートの仕組み

外側のループは i = 0 から n − 2 まで進みます。位置 i が次に確定する場所です。各走査の最初に min_idx = i とし、j を i + 1 から n − 1 まで進めます。

arr[j] < arr[min_idx] なら、最小値の候補を min_idx = j に更新します。走査後、min_idx != i の場合だけ arr[min_idx] と arr[i] を交換します。

第 i 回が終わると、先頭の i + 1 個には小さい順に確定した値が並びます。バブルソートが右側を確定するのに対し、選択ソートの確定領域は左側から広がります。

選択ソートのステップ

既定の入力は [25, 49, 25, 64, 12, 37, 15] です。最初の25を 25a、次の25を 25b とすると、安定性を確認できます。

第1回、i = 0 で候補は25aです。49は大きく、25bは等しいため、厳密な < では候補を更新しません。64も大きく、添字4の12で候補を更新します。37と15は12より大きいので、最後に添字0と4を交換します。結果は [12, 49, 25b, 64, 25a, 37, 15] です。

12は最終位置に入りますが、25aは25bを越えました。最初の交換だけで元の順序が逆転しています。選択ソートは不安定です。

第2回は添字1の49から最小値を探します。25が候補になり、最後に添字6の15が選ばれます。交換後は [12, 15, 25b, 64, 25a, 37, 49] です。

第3回は添字2の25bが残りの最小値です。同じ値の25aでは候補を更新せず、交換もしません。走査だけで1位置が確定します。

第4回は25aを添字3へ移し、[12, 15, 25b, 25a, 64, 37, 49]。第5回は37を選び、[12, 15, 25b, 25a, 37, 64, 49]。第6回は49を選び、[12, 15, 25b, 25a, 37, 49, 64] になります。

アニメーションでは j が未整列部分を走査し、min が最小値の候補を追います。交換は毎回必ず起こるわけではなく、1走査につき最大1回です。

時間・空間計算量

比較回数は常に n(n − 1) / 2 です。一方、交換は最大 n − 1 回なので O(n) に収まります。追加空間は O(1) です。

この実装は if min_idx != i で不要な交換を省きます。要素の移動が比較より高価な場合、交換の少なさが利点になります。ただし整列済みでも比較を省けないため、入力の既存の順序には適応しません。

境界条件

• 空配列・1要素：外側のループを実行しません。
• 整列済み：毎回 min_idx == i となり、交換は0回です。比較は O(n²) のままです。
• 全要素が同じ：厳密な < が成立せず、候補更新も交換も起こりません。
• 重複値：長距離の交換で元の順序が変わります。最小例は [2a, 2b, 1] から [1, 2b, 2a] への変化です。

よくある間違い

• min_idx = i を毎回設定しない：前回の候補が残り、違う領域を参照します。
• arr[min_idx] ではなく arr[i] と比較する：それまでの最小値を保持できません。候補が正しい最小値でなくなることがあります。
• 無条件で交換する：min_idx != i の確認がないと、同じ位置との交換が増えます。
• 安定だと考える：同じキーを持つ記録の順序が必要なら、挿入ソート、マージソート、Timsort などの安定ソートを選びます。