アルゴリズムとデータ構造編【整列】 第2章 選択ソート

先頭へ戻る

この章の概要

この章の概要です。


選択ソート

この章では、選択ソートを取り上げます。

単純選択ソートと呼ばれることもあります。

選択ソートは、データ列の中で一番小さい(降順に並べ替える場合は一番大きい)データを探し、そのデータと先頭のデータとを交換します。次に、2番目に小さい(または大きい)データと、先頭から2番目のデータとを交換します。これをデータ列の末尾に行き着くまで繰り返すと、ソートが完了するというものです。

詳しい手順を見ていきましょう。

int array[] = {7, 2, 4, 5, 1, 6};

この配列を昇順にソートします。

まず、一番小さいデータを探します。これは先頭から順番に調べていけば分かることで、結果は array[4] の位置にある 1 だと分かります。そうしたら、これを array[0] の位置に移動させればいいのですから、array[0] と array[4] を交換します。

{1, 2, 4, 5, 7, 6};

次に、2番目に小さいデータと、array[1] とを交換する過程に入ります。2番目に小さいデータは array[1] の位置にある 2 ですから、array[1] 同士の交換になります。よって、配列に変化はありません。

3番目と4番目も同じ理由で、配列に変化は起こりません。

5番目に小さいデータは、array[6] の位置にある 6 ですから、array[5] と array[6] で交換します。

{1, 2, 4, 5, 6, 7};

6番目に小さいデータを探しても、もう交換相手はいませんから、この段階で完了できます。

前章で扱った単純ソートと比べると、データ列の先頭から順番に1つずつ確定させていくという点は完全に同じです。実際、選択ソートは、単純ソートにあった無駄を省くように書き換えただけの改良版とみなせます

単純ソートの無駄というのは、一番小さいデータなのかどうかが確定していないうちから、先頭の要素との交換を行ってしまっていることです。選択ソートでは、一番小さいデータであることが確定してから交換を行うので、単純ソートよりも交換回数を減らせます。


プログラム例

では、先ほどの過程を元に、実際のプログラムを書いてみましょう。

#include <stdio.h>

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

static void selection_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 4, 5, 1, 6};

    print_array( array, SIZE_OF_ARRAY(array) );
    selection_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    選択ソート (昇順)
*/
void selection_sort(int* array, size_t size)
{
    size_t i, j;
    int min_index;

    for(i = 0; i < size - 1; ++i){
        min_index = i;
        for(j = i + 1; j < size; ++j){
            if(array[min_index] > array[j]){
                min_index = j;
            }
        }
        SWAP(int, array[i], array[min_index]);
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    size_t i;

    for(i = 0; i < size; ++i){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果:

7 2 4 5 1 6
1 2 4 5 6 7

選択ソートをしているのは、selection_sort関数の中です。変数min_index は、一番小さいデータの位置を表しています。ここでいう「一番小さい」は、まだソート後の位置が確定していないデータの中で「一番小さい」ということです。

前章の単純ソートのサンプルプログラムと比較してみれば、SWAPマクロを通る回数が減らせることが理解できると思います。単純ソートでは、元のデータ列の並び次第で幾度となく交換が行われますが、選択ソートでは、外側のループを1周するたびに、交換が1回だけ行われるようになっています。

性能

選択ソートの計算量は O(n2) で、遅い整列アルゴリズムだと言えます。この計算量は、単純ソートと同じですが、交換回数が少なくすむ可能性が高いので、普通は選択ソートの方が高速になります。

なお、選択ソートは安定なアルゴリズムではありません

実際に、単純ソートと性能比較をしておきましょう。ここでは、それぞれのアルゴリズムは、コードライブラリの ppps_int_sort を使うようにしています。実装は、これまでの章での解説通りのものになっていると考えて頂いて結構です。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_sort.h"

#define ARRAY_SIZE              10000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

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

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


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_simple_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("simple_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_selection_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("selection_sort");

    return 0;
}

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

    srand(0);

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

実行結果:

simple_sort: 0.419000 seconds
selection_sort: 0.187000 seconds

10000個の要素を持つ配列を、乱数で適当に初期化したものを、単純ソートと選択ソートによって昇順にソートしています。実行結果にあるように、選択ソートの方が良い結果を示しました。

この差は、交換回数の少なさから来ているので、それぞれの場合の交換回数も調べてみると良いでしょう。これは練習問題に残しておきます。

まとめ

選択ソートの計算量は O(n2) で、これは遅いアルゴリズムだと言えます。また、安定なソートではありません

単純ソート(第1章)と同じ計算量ですが、交換回数が減らせるため、選択ソートの方が高速になることが多いです。仕組みが単純ソートと似ており、プログラムもそれほど大きく変わらないので、単純ソートを使うぐらいならば、選択ソートを使った方がいいでしょう。


練習問題

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

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


解答ページはこちら

参考リンク



更新履歴

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

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

'2013/1/19 性能調査を、コードライブラリのソースを使って行うように変更。

'2012/6/23 コードライブラリのパス変更に伴い、リンクを修正。

'2012/5/6 新規作成。



前の章へ(第1章 単純ソート)

次の章へ(第3章 バブルソート)

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

Programming Place Plus のトップページへ


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