選択ソートとは、要素の中から最小のものを見つけ出し、先頭にもっていくことを繰り返す整列アルゴリズムです。
最後の1個を確認するまで「一番小さい」かどうかはわからないため、結局全ての要素を確認する事になります。交換回数は少ないのでバブルソートよりは高速と言えますが、実行効率は良いとはいえません。なお、計算量は「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); }