選択ソート

選択ソート（）は、ソートのアルゴリズムの一つ。
配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。
最悪時間計算量は と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。
選択ソートは内部ソートである。また、安定ソートではない。
選択ソートの改良として、ヒープソートが挙げられる。
アルゴリズム.
選択ソートは以下の手順で行う：
上記は昇順への並べ替えだが、降順の場合も同様に、最小値でなく最大値を検索することで実現できる。
また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、と呼ばれる。
擬似コード.
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　
太字はソート完了した部分
計算時間.
以下、ソートする配列の要素数を とする。
要素の比較に関して、各ループで 回、 回、……と行われ、処理全体としては formula_1 回行われる。
要素の交換に関して、各ループで最大1回行われ、処理全体では多くとも 回となる。
バブルソートと比較すると、要素の比較回数は同じだが交換回数が少ないため、選択ソートの方が高速である。
安定性.
選択ソートは安定ソートではなく、複数の同値の要素を持つ配列に対して、同値の要素同士の順序は保存されない。
例えば配列 (2a 2b 1) に対して選択ソートを行うと、
となる（2a, 2b は同値とする）。ソートの前後で 2a, 2bの順序が変更されており、安定でないことが確かめられる。
実装.
Python.
Python での実装例を示す。
In-place 版の実装は以下の通り。
def minIndex(x, i):
 mi = i
 for j in range(i + 1, len(x)):
 if x[j] < x[mi]:
 mi = j
 return mi
def swap(x, i, j):
 x[i], x[j] = x[j], x[i]
def inplaceSelectionSort(seq):
 for i in range(len(seq)):
 mi = minIndex(seq, i)
 swap(seq, i, mi)
非 in-place 版は上記に配列のコピーを渡すことで実現できるが、例えば以下のように直接実装することもできる。
def nonInplaceSelectionSort(seq):
 ind = [*range(len(seq))]
 res = [] 
 for i in range(len(seq)):
 k = 0
 for j in range(len(ind)):
 if seq[ind[j]] < seq[ind[k]]:
 k = j
 res.append(ind.pop(k))
 return [seq[i] for i in res]
C#.
C# での実装は以下の通り。
namespace Algorithms
class SelectionSort
 static void sort(int[] x) {
 for(int i = 0; i < x.Length; i++) {
 int min = i;
 for(int j = i + 1; j < x.Length; j++) {
 if(x[j] < x[min]) {
 min = j;
 int t = x[i];
 x[i] = x[min];
 x[min] = t;
Scheme.
Scheme での実装を以下に示す。
(require-extension srfi-1) ; 実装依存。SRFI-1 と言うライブラリを用いる。
 (let loop ((ls ls) (acc '()))
 (if (null? ls)
 (reverse acc)
 (let ((x (apply min ls)))
 (loop (remove (lambda (y)
 (= y x)) ls) (cons x acc))))))