選択ソートとは、要素の中から最小のものを見つけ出し、先頭にもっていくことを繰り返す整列アルゴリズムです。
最後の１個を確認するまで「一番小さい」かどうかはわからないため、結局全ての要素を確認する事になります。交換回数は少ないのでバブルソートよりは高速と言えますが、実行効率は良いとはいえません。なお、計算量は「O(n^2)」となります。
最小の要素を見つけ出して、前の要素と交換していきます。
[before]:2 6 5 3 1 4 ---------[1 round]--------- 1 6 5 3 2 4 ---------[2 round]--------- 1 2 5 3 6 4 ---------[3 round]--------- 1 2 3 5 6 4 ---------[4 round]--------- 1 2 3 4 6 5 ---------[5 round]--------- 1 2 3 4 5 6 [after]:1 2 3 4 5 6
#include <stdio.h>
static void
array_print(int *array, unsigned int size)
{
int i = 0;
for(i = 0; i < size; i++){
printf("%d ", array[i] );
}
putchar('\n');
}
/*!
* @brief 選択ソートを行う
* @param[in/out] array 整列する要素配列
* @param[in] size 配列のサイズ
*/
void
selection_sort(int *array, unsigned int size)
{
int i, j, temp;
int low_index = 0; /* 最小要素の位置情報 */
for(i = 0; i < size - 1; i++){
printf("---------[%d round]---------\n", i + 1);
/* 最小の要素位置を探す */
low_index = i;
temp = array[i];
for(j = i + 1; j < size; j++){
if(array[j] < temp){
low_index = j;
temp = array[j];
}
}
/* 最小の要素を移動する */
temp = array[i];
array[i] = array[low_index];
array[low_index] = temp;
array_print(array, size);
}
}
int
main(void)
{
int data[] = {2,6,5,3,1,4};
printf("[before]:");
array_print(data, sizeof(data)/4);
selection_sort(data, sizeof(data)/4);
printf("[after]:");
array_print(data, sizeof(data)/4);
return(0);
}