選択ソートとは
最小値（または最大値）を見つけて、先頭に移動。2番目に小さい（または大きい）要素を見つけて、2番目に移動。これを 要素数-1番目 まで繰り返して、整列するアルゴリズム。
分かりやすいが、遅い。安定ではない。
サンプルコード
ここでは、int型の配列を、選択ソートを用いて小さい順に並べ替える。
selection_sort.c
# include<stdio.h>
/* 値を交換する関数 */
void swap (int *x, int *y) {
int temp; // 値を一時保存する変数
temp = *x;
*x = *y;
*y = temp;
}
/* 選択ソート */
void selection_sort (int array[], int array_size) {
int i, j, min_index;
for (i = 0; i < array_size-1; i++) {
min_index = i; // 先頭要素が一番小さいとする
for (j = i + 1; j < array_size; j++) {
if (array[j] < array[min_index]) { min_index = j; } // 値の比較、最小値の更新
}
swap(&array[min_index], &array[i]); // 最小値と先頭要素を交換
}
}
int main (void) {
int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
int i;
printf("Before sort: ");
for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
printf("\n");
selection_sort(array, 10);
printf("After sort: ");
for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
printf("\n");
return 0;
}
実行結果
Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9
性能
-
要素の移動
1個当たり平均高々1回 -
比較回数
$$(n-1)+(n-2)+\cdots +1=\sum^{n-1}_{i=1}{(n-i)}=n(n-1)/2\to O(n^2)$$
- 交換回数（swap回数）
- n-1回
- 要素数が多い場合、実用性は低い