選択ソートとは

最小値（または最大値）を見つけて、先頭に移動。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回
- 要素数が多い場合、実用性は低い