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

バブルソート

今回からはソートアルゴリズムについて説明していきます。
ソートアルゴリズムとは、データの順番を並び替える方法のことです。
まずはバブルソートについて説明します。

例えば↓のようにランダムの数字が入った5つの要素を持つ配列があるとします。

３

６

７

４

１

これを一つ一つ、後ろから一つ前の要素と比較していきます。
まず、１と4を比較します。１の方が小さいので、4の要素と入れ替えます。

３

６

７

１

４

次にまた次の要素と比較します。
つまり１と７を比較します。1の方が小さいのでまた入れ替えます。

３

６

１

７

４

こうなりますね。
これを繰り返していくと

１

３

６

７

４

最終的に1が一番前に来ますね。
全ての要素と比較した上で、1が一番小さいとわかったのですから、
1の値がこの要素の中で一番小さい値だということが確定したことがわかりますね？
ですので、もう最初の要素は比較する必要がありません。
後はまた、後ろから順番に比較していきます。
進めていくと、４と３の比較のところで、3の方が小さいのでここで交換は行われません。
次の１と３の比較はもう最初にして１が小さいと確定してるので、比較する必要もありません。
これを全ての要素に対して繰り返していくことで、データの並び替えを行う方法をバブルソートと言います。
単純に比較していくだけなので、単純ソートとも呼ばれます。

あとはこれをコードで表現するだけです。

#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 temp=0;

	for(int i=0;i<number;++i){
		
		//後ろから順番にチェックしていく
		for(int s=number-1;s>i;--s){
			//一つ下の要素と比較
			if(test[s]<test[s-1]){
				//一時的に退避
				temp=test[s-1];
				//交換
				test[s-1]=test[s];
				//退避してたやつを戻す
				test[s]=temp;
			}
		}
	}
	//ソートされてるか表示
	for(int i=0;i<number;++i){
		printf("%d,",test[i]);
	}
	puts("");

	return 0;

まず、順番がバラバラで値が入っている配列を用意し、要素数を取得します。
まず、最初のfor文ですが、全要素チェックするため、要素数分のループを回る必要があるので、要素数分ループしてます。
次のforループで、
後ろの要素から比較していくので、最後の要素番号(つまり要素数ｰ1)からiの値まで順番に比較していっています。
もし、比較対象が小さければ、値を交換してます。
全部比較が終わったら、一つの上のfor文に戻ってiが１増えますよね？
これが確定した数字を表しています。
次のループに入ると、ループ条件はs>iとなっているので、iが１増えると最初の要素は比較されないことがわかります。
これで先程説明したバブルソートが実現できていることがわかります。
最後に表示した結果を見ていただければ、ちゃんとソートが出来ていることがわかります。

以上がバブルソートの説明です。
次は選択ソートの説明をします。


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