選択ソートで配列を並び替える

選択ソートを使用する

選択ソート (selection sort) は、未整列の範囲から 最小（または最大）の要素を1つ選び、先頭側の未確定位置と交換することを繰り返す比較ソートである。各パスで「確定する要素」がはっきりするため、バブルソート と同様に挙動を追いやすく、初学者向けの題材としてよく登場する。

1. 外側のインデックス: 確定済みでない左端を i とする（初期は i = 0）。
2. 最小の探索: j を i+1 から末尾まで動かし、A[i..] の中で最小の要素の位置を minIdx として記録する（A[j] と現時点の最小 A[minIdx] を比較する）。
3. 交換: minIdx ≠ i なら A[i] と A[minIdx] を入れ替える。これで位置 i の値は全体の中で i 番目に小さいものに確定する。
4. 繰り返し: i を1つ進め、i = n-2 まで繰り返す（残り1要素は自動的に最大側に位置する）。

procedure selection_sort(A)
  n = length(A)
  for i from 0 to n - 2
    minIdx = i
    for j from i + 1 to n - 1
      if A[j] < A[minIdx] then
        minIdx = j
    if minIdx != i then
      swap(A[i], A[minIdx])

最悪・平均・最良いずれも 比較回数は O(n²) で、入力の並びで大きくは変わらない。交換回数は高々 O(n) と少ないのが特徴である。追加配列を使わなければ 空間計算量は O(1) のインプレースソート。等しい値同士の順序を入れ替える実装になりやすく、一般に 不安定 なソートとして扱われる。

クイックソート やマージソートと比べると漸近的な効率は劣るが、実装が短く、動きの説明に向く。

実装が単純な分、入力サイズが大きい場面では標準ライブラリのソートやより漸近的に有利なアルゴリズムに任せるのが現実的である。