選択ソート

http://www.geocities.jp/ky_webid/algorithm/003.html

お次は選択ソートの話です。

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す（厳密には、データ列の最後より１つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。大小が入れ替わる降順の場合も同様の手法。

選択ソート - Wikipedia

ソート方法はバブルソートよりも単純そうですね。ただし、配列の要素を全部走査してそれを何度も繰り返すので時間効率はかなり悪そうです。

とりあえず実装してみます。

#include <stdio.h>

#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

void selection_sort (int *data,int array_size) {
    int i,j;
    int work,*min;
    
    if ( array_size <= 1 ) {
        return;
    }
    
    // 最後の要素までチェックする必要は無いのでarray_size-1まででよい。
    for(i=0;i<array_size-1;i++) {
        min = &data[i];
        for(j=i;j<array_size;j++) {
            if ( *min > data[j] ) {
                min = &data[j];
            }
        }
        work = data[i];
        data[i] = *min;
        *min = work;
    }
}

int main (void) {
    int num[] = { 3,9,11,50,6,34,20,98,6,1 };
    int i;
    
    selection_sort(num,ARRAY_NUM(num));
    
    for(i=0;i<ARRAY_NUM(num);i++){
        printf("%d ",num[i]);
    }
}

今回はどうでしょう。割と問題なく実装できたように思えます。いつもみたいにwhileは使わずにやっていますし・・・。

初め最小値の場所の格納をどうしようか悩んでいたのですが、添え字を保存するよりポインタをそのまま持てば良いということに気付き、今の形になりました。

解答例との比較

ほぼ同じ実装で安心しました。

解答例の方では最小値の他に、その最小値の添え字も保存していますね。

これはどちらでも良いのだと思います。ポインタだと不味い理由があるのかもしれませんが大丈夫でしょう。