バブルソート C言語

#バブルソートとは
##はじめに
　まずはじめにバブルソートとはソーティングアルゴリズムの一つである。単純であるため実装しやすいがこのアルゴリズムでは効率が悪い。

実際に表でイメージしてみる

　　 5つの要素が入ったの配列a[]を用意して,昇順の場合を考えてみる。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	6	4	9	2	8
※昇順（a[0]から数が小さい順）で行った場合

１．バブルソートは端のa[３]とa[４]の要素の大きさを比べていく。配列番号の２つa[n - 1]とa[n]を比較してa[n - 1]の要素がa[n]の要素より大きい場合に要素の交換を行う。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	6	4	9	2	8
a[3] < a[4]であるためにa[3]とa[4]の要素の交換は行わない。

２．次にa[2]とa[3]の要素の大きさを比べる。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	6	4	9	2	8
a[2] > a[3]であるため、a[2]とa[3]の要素の交換が行われる。よって表は、

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	6	4	２	９	8
となる。
３．このように次はa[1]とa[2]の比較を行い、最後にa[0]とa[1]の比較を行う。(省略)
要素2がa[0]に登ってくる。２は一番小さい数ということがわかるため今後の比較には必要がなく配列番号a[0]の値は固定される。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	2	6	4	9	8
４．次にまた同じようにa[3]とa[4]の比較を行う。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	2	6	4	9	8
a[3] > a[4]であるため、a[3]とa[4]の要素は交換される。よって、

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	2	6	4	８	９
となる。
５．また同じようにa[2]とa[3]、a[1]とa[2]の比較を順に行いa[1]の要素が決定される。

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	2	４	６	８	９
たまたま昇順に並んでしまったがこのあともa[2],a[3]の値を決定するために比較を繰り返す。

６．

配列番号	a[0]	a[1]	a[2]	a[3]	a[4]
要素	2	6	4	8	9
このような要素が昇順になったら終了である。

##このアルゴリズムをC言語で再現する

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define NUM 10000
#define NUM_M 10000

void swap(int *a, int *b){
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;

}
void buble(int data[]){
	int i,j;
	for(i = 0; i < NUM; i++){
		for(j = NUM-1; j > i; j-- ){
			if(data[j-1] > data[j]){
			swap(&data[j],&data[j-1]);
		}
			}
				}
}
int main(void){

	int n,k;
	int data[NUM];
	clock_t start_time,end_time;
	
	srand(time(NULL));

	for(k = 0; k < NUM; k++){
		data[k] = rand() % NUM_M; 
	}
	
	start_time = clock();

	buble(data);

	end_time = clock();
		printf("%s: data[%d] = {","bubblesort",NUM);
	for(n = 0;n < NUM; n++){
		printf("%2d,",data[n]);
	}
	printf("}\n");
	printf("time: %f 秒\n",(double)(end_time - start_time)/CLOCKS_PER_SEC);

	return 0;
}

##解説
　このプログラムはバブルソートを行いバブルソートで配列を昇順にするのにかかった時間を計測する。マクロ定義されているNUMは配列の数であり今回は１００００に設定している。NUM_Mは１００００で設定した場合０から１００００未満のランダムの数を要素の数にすることとする。

###ランダムな数を配列dataに格納

srand(time(NULL));

	for(k = 0; k < NUM; k++){
		data[k] = rand() % NUM_M; 
	}

　srand関数で中をtimeにすることで毎回ランダムな数を作ることができる。また、for文を使って配列NUM個の中にランダムな要素を格納する。

###swap解説

void swap(int *a, int *b){
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

　この関数は変数aと変数bの値を交換することができる。変数tmpにaの値を代入する。次に、変数aにbの値を代入する。最後に変数bにaの値が入っている変数tmpを代入する。この動作によって変数aと変数bの値が交換できた。*（ポインタ）については今後説明する。ポインタがないと値の交換がうまく行かない。
###bubble解説

void buble(int data[]){
	int i,j;
	for(i = 0; i < NUM; i++){
		for(j = NUM-1; j > i; j-- ){
			if(data[j-1] > data[j]){
			swap(&data[j],&data[j-1]);
		}
			}
				}
}

　配列はNUM個あるため１つずつ要素を固定していくために変数iを+１していきNUM未満まで繰り返し行う。iの数は配列の固定されている個数と考えて、次に配列と配列は（NUM-１）回比較されるため変数jの初期値はNUM-1とする。またその時、固定されている配列が増えていくためにj > iになるまでjをー１ずつしていく。そして昇順になるように比較している配列の小さい方（data[j-1]）が（data[j]）より大きいとき配列の要素を交換する。（降順にしたい場合は不等号の向きを逆にすればいい）。