選択ソート

クラス	ソート
データ構造	配列
最悪計算時間	О(n²)
最良計算時間	О(n²)
平均計算時間	О(n²)
最悪空間計算量	О(n) total, O(1) auxiliary

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。

最良時間計算量は O(n²) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。

選択ソートは内部ソートである。また、安定ソートではない。

選択ソートの改良として、ヒープソートが挙げられる。

選択ソートは以下の手順で行う：

1. 1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる）
2. 以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する
3. すべての要素がソート済みになったら処理を終了する

上記は昇順への並べ替えだが、降順の場合も同様に、最小値でなく最大値を検索することで実現できる。

また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、double selection sortと呼ばれる。

for I := 1 to N
  min := I
  for J := I+1 to N  
    if data[J] < data[min] then
      min := J
    end if
  end for
  swap(data[I], data[min])
end for

初期データ: 8 4 3 7 6 5 2 1　

太字はソート完了した部分

1 4 3 7 6 5 2 8 （1回目のループ終了時）

1 2 3 7 6 5 4 8 （2回目のループ終了時）

1 2 3 7 6 5 4 8 （3回目のループ終了時）

1 2 3 4 6 5 7 8 （4回目のループ終了時）

1 2 3 4 5 6 7 8 （5回目のループ終了時）

この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。

1 2 3 4 5 6 7 8 （6回目のループ終了時）

1 2 3 4 5 6 7 8 （7回目のループ終了時）

以下、ソートする配列の要素数を n とする。

要素の比較に関して、各ループで n − 1 回、n − 2 回、……と行われ、処理全体としては ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}}$ カテゴリ