先頭へ戻る

選択ソート 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第2章

Programming Place Plus トップページアルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 降順にソートする選択ソートを作成してください。


本編のサンプルプログラムで使った selection_sort関数を修正してみます。

/*
    選択ソート (降順)
*/
void selection_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){

        // 第 i 位となる値の位置を探す
        size_t max_index = i;
        for( size_t j = i + 1; j < size; ++j ){
            if( array[max_index] < array[j] ){
                max_index = j;
            }
        }

        // 第 i 位の値をもつ要素と、array[i] を交換する
        SWAP(int, array[i], array[max_index]);
    }
}

if文の不等号を変えれば実現できます。探すのが一番小さい値ではなく、一番大きい値になるので、変数min_index の名前を max_index に変更していますが、これは名前を変えただけです。

問題②

問題② 単純ソートと選択ソートとで、交換回数にどれだけ差が出るかを調べてください。


simple_sort関数と selection_sort関数の中で、SWAPマクロの箇所を通過する回数をカウントしてみます。

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE              10000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void init_array(int* array, size_t size);
static void simple_sort(int* array, size_t size);
static void selection_sort(int* array, size_t size);

int main(void)
{
    int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    simple_sort( array, SIZE_OF_ARRAY(array) );

    init_array( array, SIZE_OF_ARRAY(array) );
    selection_sort( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    単純ソート (昇順)
*/
void simple_sort(int* array, size_t size)
{
    int count = 0;

    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = i + 1; j < size; ++j ){
            if( array[i] > array[j] ){
                SWAP(int, array[i], array[j]);
                count++;
            }
        }
    }
    printf( "simple_sort count: %d\n", count );
}

/*
    選択ソート (昇順)
*/
void selection_sort(int* array, size_t size)
{
    int count = 0;

    for( size_t i = 0; i < size - 1; ++i ){

        // 第 i 位となる値の位置を探す
        size_t min_index = i;
        for( size_t j = i + 1; j < size; ++j ){
            if( array[min_index] > array[j] ){
                min_index = j;
            }
        }

        // 第 i 位の値をもつ要素と、array[i] を交換する
        SWAP(int, array[i], array[min_index]);

        count++;
    }
    printf( "selection_sort count: %d\n", count );
}

実行結果:

simple_sort count: 18894182
selection_sort count: 9999

交換回数に、極端に差が出ていることが分かります。

単純ソートの交換回数はデータ列の内容によって異なりますが、選択ソートの交換回数はつねに n-1回です。これは、外側のループを1周するたびに1回の交換を行うからです。また、外側のループの条件式は「size - 1;」ですから、n回ではなく n-1回です。

ここから分かるように、選択ソートはデータ数が同じなら、データ列の内容に関わらず、ほぼ同じ時間でソートを終えられるという特性があります。


参考リンク


更新履歴

’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2012/5/6 新規作成。



第2章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー