トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > 選択整列法

配列から最小の要素を見つけて、先頭にある要素と交換していくことでソートする方法。
項目が非常に大きく、キーが小さい場合に推奨される方法。

比較回数	n(n-1)/2
交換の回数	N-1
平均計算量	O(N^2)
最悪計算量	O(N^2)

6

4

2

3

1

5

のような場合には、まず最小を6とする。
次に後ろの要素を全て辿って最小の物(この場合1)をチョイスして
先頭要素と交換する。

1

4

2

3

6

5

次に既に交換した1を除く

4

2

3

6

5

で同様の処理を繰り返すことでソートする。

javaで書いてみた

public class Selection {
public static void main(String[] args) {
	int[] array = {3,2,4,5,6,1};
	Selection select = new Selection();
	select.selection(array); //交換
                 for(int i = 0; i < array.length; i++) {
	    System.out.println(array[i]);
	}
}
public void selection(int[] array) {
	int temp;
                 /*外ループは配列の長さ-1分動かす*/
	for(int i = 0; i < array.length - 1; i++) {
	   int min = i; //とりあえず、残っている要素の先頭を最小と置く
                       /*内ループは残っている要素の2つ目から配列の最後まで動かす*/
	   for(int j = i+1; j < array.length; j++) {
		   if(array[j] <= array[min]) min = j;
                                  /*以下3行は要素を交換している*/
		   temp = array[min];
		   array[min] = array[i];
		   array[i] = temp;
	   }
	}
}
}

参考：http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88