ソートアルゴリズム (バブル・シェーカー・コム)

基本的なソートアルゴリズムのc言語による実装
バブルソート、シェーカーソート、コムソートの3つのアルゴリズムの処理時間の計算

sort.c

/* Comparing the time of shaker sort with that of bubble sort */

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
# include <time.h>

void sort_check(int *, int, int);
void swap(int *, int, int);

int main(void){

	int *a;
	int *b;

	int flag = 0;
	int step = 0, change = 0;
	int max;

	int m;
	int number_max;
	int i, j;
	int h;

	clock_t start, end;

	double bubble_time, shaker_time, comb_time;
	int bubble_step, shaker_step, comb_step;
	int bubble_change, shaker_change, comb_change;

変数の宣言
aは並び替えをするための配列、bの中身も基本的には同じ
stepは配列要素の比較回数、changeは配列要素の交換回数

sort.c

	// 配列の要素数
	m = 50000;
	number_max = 100000;
	a = (int *)malloc(sizeof(int)*m);
	b = (int *)malloc(sizeof(int)*m);

	srand((unsigned int)time(NULL));

	// insert number into an array at random
	printf("-- array --\n\n");
	for(i = 0; i < m; i++){
		b[i] = rand()%number_max;
		a[i] = b[i];
		if(i < 10 || m - 10 < i) printf("a[%d] = %d\n", i, a[i]);
	}

number_maxに関しては、
0からnumber_maxまでの整数をランダムに配列に格納する、という意味
配列の要素数は50000、number_maxは100000とした。

尚、すべて昇順である。

sort.c

	// Measuring the time of bubble short
	start = clock();

	change = 0;
	step = 0;

	for(i = m-1; i >= 0; i--){
		flag = 0;
		for(j = 0; j < i; j++){
			step++;
			if(a[j] > a[j+1]){
				flag++;
				change++;
				swap(a, j, j+1);
			}
		}
		if(flag == 0) break;
	}

	end = clock();

	sort_check(a, m, 0);

	bubble_time = (double)(end - start)/(double)CLOCKS_PER_SEC;
	bubble_step = step;
	bubble_change = change;

	// 計算時間などを表示
	printf("\n");
	printf("-- bubble sort --\n");
	printf("\n");
	printf("calculation time (bubble sort) : %lf [sec]\n", bubble_time);
	printf("\n");
	printf("comparing time : %d, changing time : %d\n", bubble_step, bubble_change);
	printf("\n");

	// バブルソート後の配列を表示
	for(int i = 0; i < m; i++)
		if(i < 10 || m-10 <= i) printf("a[%d] = %d\n", i, a[i]);

バブルソート
sort_check関数は、きちんとソートされているかどうかを判定する関数(後述)

sort.c

	for(i = 0; i < m; i++) a[i] = b[i];

	// Measuring the time of shaker sort
	start = clock();

	step = 0;
	change = 0;

	for(i = m-1; i >= 0; i--){
		flag = 0;
		for(j = m-1-i; j < i; j++){
     			step++;
			if(a[j] > a[j+1]){
				flag++;
				change++;
				swap(a, j, j+1);
			}
		}
		if(flag == 0) break;

		for(j = i-1; j > m-1-i; j--){
			step++;
			if(a[j] < a[j-1]){
				flag++;
				change++;
				swap(a, j, j-1);
			}
		}
		if(flag == 0) break;

	}

	end = clock();

	sort_check(a, m, 0);

	shaker_time = (double)(end - start)/(double)CLOCKS_PER_SEC;
	shaker_step = step;
	shaker_change = change;

	// 計算時間などを表示
	printf("\n");
	printf("-- shaker sort --\n");
	printf("\n");
	printf("calculation time (shaker sort) : %lf [sec]\n", shaker_time);
	printf("\n");
	printf("comparing time : %d, changing time : %d\n", shaker_step, shaker_change);
	printf("\n");

	// シェーカーソート後の配列を表示
	for(i = 0; i < m; i++)
		if(i < 10 || m-10 <= i) printf("a[%d] = %d\n", i, a[i]);

シェーカーソート

sort.c

	for(i = 0; i < m; i++) a[i] = b[i];

	// Measuring the time of comb short
	start = clock();

	step = 0;
	change = 0;
	flag = 1;

	h = m*10/13;

	while(h >= 1 && flag != 0){
		flag = 0;
		for(i = m-h-1; i >= 0; i--){
 			step++;
			if(a[i] > a[i+h]){
				change++;
				flag++;
				swap(a, i, i+h);
			}
		}
		if(h >= 2) h = h*10/13;

	}

	end = clock();

	sort_check(a, m, 0);

	comb_time = (end - start)/(double)CLOCKS_PER_SEC;
	comb_step = step;
	comb_change = change;

	// 計算時間などを表示
	printf("\n");
	printf("-- comb sort --\n");
	printf("\n");
	printf("calculation time (comb sort) : %lf [sec]\n", comb_time);
	printf("\n");
	printf("comparing time : %d, changing time : %d\n", comb_step, comb_change);
	printf("\n");

	// コムソート後の配列を表示
	for(i = 0; i < m; i++)
		if(i < 10 || m-10 <= i) printf("a[%d] = %d\n", i, a[i]);

コムソート

計算時間

やはり、バブル＞シェーカー＞コム となっている。

コムソートの時間のみのグラフ↓