>> C言語入門トップに戻る

選択ソート

今回は選択ソートについて説明します。

選択ソートとは最初の要素を最小値(最大値)として定めておき、
残りの要素と比較しながら、それより小さいもの(大きいもの)があれば交換するという方法です。
最初の要素の比較が終わったら、次は2番目の要素を最小値(最大値)にして、同じ比較をしたあと
今度は2番目の要素と入れ替えます。
先程のバブルソートと違って、毎回入れ替える作業が減るため若干速度的には早くなります。


例えば↑の3を最小値として設定しておきます。
その値と後ろの要素を全て比較します。
その比較した中で、一番小さい要素と値を交換します。
これを繰り返します。
さっきは毎回値を入れ替えていましたが、今回は比較がほとんどで交換が1度か0回なので若干早くなります。

下記のコードを見て下さい。

#include <stdio.h>

int main(void)
{
	int test[10]={3,10,4,5,6,1,8,7,9,2};

	//配列の要素数を取得
	int number=sizeof(test)/sizeof(int);

	//最小値の添字表す
	int index=0;
	int work;

	//要素を順番に比較
	for(int i=0;i<number;++i){

		//比較要素を最小値として、その添字を保存
		index=i;

		//最小値の添字より一つ上の添字から比較
		for(int s=i+1;s<number;++s){
			if(test[s]<test[index]){
				//もし小さいのがあれば、その添字を保存
				index=s;
			}
		}
		//一番小さかった添字の要素と現在の比較要素とを交換
		work=test[i];
		test[i]=test[index];
		test[index]=work;
	}

	//並びかえ出来たか確認
	for(int i=0;i<number;++i){
		printf("%d,",test[i]);
	}

	//改行
	puts("");

	return 0;

}

まず最初に、配列に入った要素を前から調べていくのですが、
その要素をまず最小値として添字を保存しておきます。
その値と残りの要素を比較していき、小さいものがあれば、その添字を保存しておきます。
そのループを抜ければ、変数indexにはもっとも小さい値が入ってる要素の添字が残りますよね?
あとはそれと、現在調べている比較要素の値とを入れ替えるだけです。
表示するとちゃんとソートされていることがわかりますね?

以上が、選択ソートに説明になります。
次回は挿入ソートの説明をします。


>> 【挿入ソート】に進む
>> C言語入門トップに戻る