選択ソート — ステップバイステップビジュアルガイド

選択ソートの動作原理

選択ソートは配列をソート済み部分（左）と未ソート部分（右）に分割します。各反復で、未ソート部分から最小の要素を見つけ、ソート済み部分の末尾に移動します。

アルゴリズム

for i = 0 to n-2:
  minIndex = i
  for j = i+1 to n-1:
    if arr[j] < arr[minIndex]:
      minIndex = j
  swap(arr[i], arr[minIndex])

ステップごとの例

[64, 25, 12, 22, 11] から開始：

1. [64, 25, 12, 22, 11] の最小値を検索 → インデックス4の11 → インデックス0とスワップ → [11, 25, 12, 22, 64]
2. [25, 12, 22, 64] の最小値 → インデックス2の12 → インデックス1とスワップ → [11, 12, 25, 22, 64]
3. [25, 22, 64] の最小値 → インデックス3の22 → インデックス2とスワップ → [11, 12, 22, 25, 64]
4. [25, 64] の最小値 → インデックス3の25 → スワップ不要 → [11, 12, 22, 25, 64]

主な特徴

• 常にO(n²)回の比較: バブルソートとは異なり、選択ソートは早期終了できません。入力順序に関係なく、最小値を見つけるために未ソート部分全体を常にスキャンします。
• 最小スワップ: 選択ソートは最大n-1回のスワップを実行し、これは最適です。スワップ操作が高コストな場合（フラッシュメモリへの書き込みなど）に有用です。
• 不安定: スワップ操作により、等しい要素の相対順序が変わる可能性があります。

比較回数

比較回数は常にn(n-1)/2で、正確にn²/2 - n/2です。100要素の配列では、入力順序に関係なく4,950回の比較が行われます。