ももの知恵の樹

C言語アルゴリズム-選択ソート

選択ソート(selection sort)とは

選択ソートとは、要素の中から最小のものを見つけ出し、先頭にもっていくことを繰り返す整列アルゴリズムです。

最後の１個を確認するまで「一番小さい」かどうかはわからないため、結局全ての要素を確認する事になります。交換回数は少ないのでバブルソートよりは高速と言えますが、実行効率は良いとはいえません。なお、計算量は「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

C言語による選択ソートのプログラム


#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);
}

関連ページ