選択ソート (Selection Sort)

C 言語による実装

selectionsort.c

/*
  選択ソート (Selection Sort):
  選択ソートは配列の最小値 (最大値) を持つ要素を探してそれ
  を配列の先頭要素と交換することで整列を行うアルゴリズム.
*/

/*
  アルゴリズム分析:
  1. 配列の先頭要素を仮の最小値を持つ要素 A[0] としておく
  2. A[0] と A[0] 以外の要素の値を比較して A[0] より小さい
     値を持つ要素 A[1] が見つかれば A[1] と A[0] の値を交換
     する
  3. STEP 2 を繰り返すことで A[0] には配列内での最小値がセット
     される
  4. 次は A[0] を除いて A[1] と A[1] 以外の要素, A[1] を除いて
     A[2] と A[2] 以外の要素を比較と交換をして整列が完了する
*/

/*
  注意:
  バブルソートと比較すると, [比較回数] は同じだが [交換回数] が少ない
  ので, 選択ソートのほうが高速である.
*/
 
#include <stdio.h>

void swap(int *x, int *y);
void selectionsort(int nums[], int array_size);

int main(void){
  int i;
  
  /* unsorted list */
  int list[10] = {10, 8, 15, 20, 10, 35, 25, 70, 6, 9};
  
  selectionsort(list, 10);
  
  for(i = 0; i < 10; i++){
    printf("%d ", list[i]);
  }
  printf("\n");
  
  return 0;
}

void swap(int *x, int *y){
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

void selectionsort(int nums[], int array_size){
  int i, j;
  int min; /* 最小値を持つ要素のインデックス */
  
  for(i = 0; i < array_size; i++){
    min = i;
    for(j = i + 1; j < array_size; j++){
      /* 昇順条件: < */
      /* 降順条件: > */
      if(nums[j] < nums[min]) min = j;
    }
    swap(&nums[i], &nums[min]);
  }
}

selectionsort.c の実行結果はバブルソートと同じ:

[cactus:~/code_c/ad]% ./selectionsort
6 8 9 10 10 15 20 25 35 70
[cactus:~/code_c/ad]% ./bubblesort
6 8 9 10 10 15 20 25 35 70
[cactus:~/code_c/ad]%