プログラミング修行その１：バブルソート

たまには基本的なアルゴリズムの復習をしとかないと忘れるｗ
まずは簡単なバブルソートからやってみる。
練習としてCで実装した。


配列内に値が格納されているとする。
バブルソートは、左の値が右の値より大きければ入れ替えるだけ。
それを左端から右端までやる。
そうすると最大値が右端に来る。
これを配列の要素数-1だけ繰り返す。
そんだけｗ
バブルソートの実装はすぐにできた。
むしろファイルの読み込みとかで苦戦したorz
Cメンドクセー！
テスト用のファイルは2つ。
１行目の値はソートする値の数。
「sorting.txt」

100
14.87764 79.91459 32.04577 52.47648 37.37609
92.92702 95.66952 12.44020 79.36001 58.55178
45.7271 50.34571 64.64258 44.16959 80.47934
77.84812 36.76213 59.63012 14.71282 51.97675
23.64163 8.721956 29.20096 4.217992 45.30573
77.46075 62.69849 7.304937 41.10914 88.78288
78.64944 28.69343 20.21519 86.04278 86.71323
73.7722 32.83814 32.05642 50.90693 93.62222
33.20098 19.04709 24.12797 57.44827 8.226496
3.016102 18.80332 63.08548 32.34478 48.01698
75.35823 59.00964 88.93037 88.97937 40.26842
10.32882 54.73123 45.87262 68.84773 70.79227
0.2335615 70.41457 13.86259 62.18793 73.53001
67.42753 50.306 65.18794 5.185891 41.06601
90.83678 53.06632 50.26822 81.68491 92.29141
85.35683 80.62988 20.71659 44.08074 14.66574
7.861154 23.08027 88.06054 73.81652 96.86138
58.21597 3.407331 56.66343 67.48117 50.70082
56.70293 36.16603 15.31543 31.35736 68.83037
10.46522 23.64201 56.16076 75.30015 60.66254

途中経過を見たい場合は次のファイルを使う。
さすがに100個のデータのソートの途中経過は見たくないｗ
「sorting2.txt」

10
59 13 38 91 48 27 66 45 13 38

で、これがCで実装したコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LENGTH 200 // 1行の文字数
void print_numbers(double *numbers,int size); // 配列内の値を表示
int my_bubble_sort(double *numbers,int size); // バブルソート関数
int my_bubble_sort2(double *numbers,int size); // バブルソート関数(途中経過表示)
int main(int argc, char *argv[])
{
	FILE *input;
	char str[LENGTH];
	char *p;
	int size; // ソートする値の数
	double num;
	double *numbers;
	int cnt;
	// パラメータのチェック
	if( argc != 3 || argv[1][0] != '-'){
		printf("%s%s%s%s",
				"パラメータが不適切です。\n",
				"使用法：mySorting <アルゴリズム> <ファイル名>\n",
				"アルゴリズムの指定\n",
				"\t-b バブルソート"
				);
		return 0;
	}
	
	// 入力ファイルを開く
	if( (input = fopen( *(argv+2), "r") ) == NULL){
		printf("Open Input File Error.\n");
		return 0;
	}
	// 値を配列に格納する
	if( fgets(str,LENGTH,input) == NULL ){
		printf("Read Input File Error.\n");
		return 0;
	}
	size = atoi(str);
	printf("size = %d\n",size); // 値の数の確認
	numbers = malloc( sizeof(double)*size);// 配列の動的確保
	cnt = 0;
	while( fgets(str,LENGTH,input) != NULL ){
		p = strtok(str," ");
		while( p != NULL){
			num = atof(p);
			numbers[cnt] = num;
			cnt++;
			p = strtok(NULL," ");
		}
	}
	// 配列に格納された値を出力して確認
	print_numbers(numbers,size);
	// 入力ファイルを閉じる
	if( fclose(input)==EOF ){
		printf("Close Input File Error.\n");
		return 0;
	}
	
	// アルゴリズムの実行
	switch(argv[1][1])
	{
		case 'b':
			printf("バブルソート(bubble sort)\n");
			my_bubble_sort(numbers,size);
			break;
		case 'B':
			printf("バブルソート(bubble sort)\n");
			my_bubble_sort2(numbers,size);
			break;
				
		default:
			printf("アルゴリズムの指定が不適切です。\n");
			return 0;
	}
	// ソート後の配列に格納された値を出力して確認
	// ソート後、左の値が右の値より大きければエラー
	printf("ソート完了\n");
	for(cnt = 0; cnt < size; cnt++){
		printf(" %f",numbers[cnt]);
		if( cnt != 0 && numbers[cnt-1] > numbers[cnt] ){
			printf("\nerror.\n");
			return 0;
		}
		if( (cnt+1) % 5 == 0 ){
			printf("\n");
		}
	}
	return 0;
}
// 配列内の値を表示
void print_numbers(double *numbers,int size)
{
	int cnt;
	for(cnt = 0; cnt < size; cnt++){
		printf(" %f",numbers[cnt]);
		if( (cnt+1) % 5 == 0 ){
			printf("\n");
		}
	}
}
// バブルソート関数
int my_bubble_sort(double *numbers,int size)
{
	double keep;
	int i,j;
	for(j = 0; j < size-1; j++){
		for( i = 0; i < (size-j-1); i++){
			if( numbers[i] > numbers[i+1] ){
				keep = numbers[i];
				numbers[i] = numbers[i+1];
				numbers[i+1] = keep;
			}
		}
	}
	return 0;
}
// バブルソート関数2(途中経過を表示)
int my_bubble_sort2(double *numbers,int size)
{
	double keep;
	int i,j,k;
	for(j = 0; j < size-1; j++){
		for( i = 0; i < (size-j-1); i++){
			if( numbers[i] > numbers[i+1] ){
				keep = numbers[i];
				numbers[i] = numbers[i+1];
				numbers[i+1] = keep;
				print_numbers(numbers,size);
				printf("\n");
			}
		}
	}
	return 0;
}

実行結果
「sorting.txt」での実行結果

C:\C_syugyo>mySorting -b mysorting.txt
size = 100
 14.877640 79.914590 32.045770 52.476480 37.376090
 92.927020 95.669520 12.440200 79.360010 58.551780
 45.727100 50.345710 64.642580 44.169590 80.479340
 77.848120 36.762130 59.630120 14.712820 51.976750
 23.641630 8.721956 29.200960 4.217992 45.305730
 77.460750 62.698490 7.304937 41.109140 88.782880
 78.649440 28.693430 20.215190 86.042780 86.713230
 73.772200 32.838140 32.056420 50.906930 93.622220
 33.200980 19.047090 24.127970 57.448270 8.226496
 3.016102 18.803320 63.085480 32.344780 48.016980
 75.358230 59.009640 88.930370 88.979370 40.268420
 10.328820 54.731230 45.872620 68.847730 70.792270
 0.233562 70.414570 13.862590 62.187930 73.530010
 67.427530 50.306000 65.187940 5.185891 41.066010
 90.836780 53.066320 50.268220 81.684910 92.291410
 85.356830 80.629880 20.716590 44.080740 14.665740
 7.861154 23.080270 88.060540 73.816520 96.861380
 58.215970 3.407331 56.663430 67.481170 50.700820
 56.702930 36.166030 15.315430 31.357360 68.830370
 10.465220 23.642010 56.160760 75.300150 60.662540
バブルソート(bubble sort)
ソート完了
 0.233562 3.016102 3.407331 4.217992 5.185891
 7.304937 7.861154 8.226496 8.721956 10.328820
 10.465220 12.440200 13.862590 14.665740 14.712820
 14.877640 15.315430 18.803320 19.047090 20.215190
 20.716590 23.080270 23.641630 23.642010 24.127970
 28.693430 29.200960 31.357360 32.045770 32.056420
 32.344780 32.838140 33.200980 36.166030 36.762130
 37.376090 40.268420 41.066010 41.109140 44.080740
 44.169590 45.305730 45.727100 45.872620 48.016980
 50.268220 50.306000 50.345710 50.700820 50.906930
 51.976750 52.476480 53.066320 54.731230 56.160760
 56.663430 56.702930 57.448270 58.215970 58.551780
 59.009640 59.630120 60.662540 62.187930 62.698490
 63.085480 64.642580 65.187940 67.427530 67.481170
 68.830370 68.847730 70.414570 70.792270 73.530010
 73.772200 73.816520 75.300150 75.358230 77.460750
 77.848120 78.649440 79.360010 79.914590 80.479340
 80.629880 81.684910 85.356830 86.042780 86.713230
 88.060540 88.782880 88.930370 88.979370 90.836780
 92.291410 92.927020 93.622220 95.669520 96.861380

「sorting2.txt」での実行結果

C:\C_syugyo>mySorting -B mysorting2.txt
size = 10
 59.000000 13.000000 38.000000 91.000000 48.000000
 27.000000 66.000000 45.000000 13.000000 38.000000
バブルソート(bubble sort)
 13.000000 59.000000 38.000000 91.000000 48.000000
 27.000000 66.000000 45.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 91.000000 48.000000
 27.000000 66.000000 45.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 91.000000
 27.000000 66.000000 45.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 27.000000
 91.000000 66.000000 45.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 27.000000
 66.000000 91.000000 45.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 27.000000
 66.000000 45.000000 91.000000 13.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 27.000000
 66.000000 45.000000 13.000000 91.000000 38.000000

 13.000000 38.000000 59.000000 48.000000 27.000000
 66.000000 45.000000 13.000000 38.000000 91.000000

 13.000000 38.000000 48.000000 59.000000 27.000000
 66.000000 45.000000 13.000000 38.000000 91.000000

 13.000000 38.000000 48.000000 27.000000 59.000000
 66.000000 45.000000 13.000000 38.000000 91.000000

 13.000000 38.000000 48.000000 27.000000 59.000000
 45.000000 66.000000 13.000000 38.000000 91.000000

 13.000000 38.000000 48.000000 27.000000 59.000000
 45.000000 13.000000 66.000000 38.000000 91.000000

 13.000000 38.000000 48.000000 27.000000 59.000000
 45.000000 13.000000 38.000000 66.000000 91.000000

 13.000000 38.000000 27.000000 48.000000 59.000000
 45.000000 13.000000 38.000000 66.000000 91.000000

 13.000000 38.000000 27.000000 48.000000 45.000000
 59.000000 13.000000 38.000000 66.000000 91.000000

 13.000000 38.000000 27.000000 48.000000 45.000000
 13.000000 59.000000 38.000000 66.000000 91.000000

 13.000000 38.000000 27.000000 48.000000 45.000000
 13.000000 38.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 48.000000 45.000000
 13.000000 38.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 45.000000 48.000000
 13.000000 38.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 45.000000 13.000000
 48.000000 38.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 45.000000 13.000000
 38.000000 48.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 13.000000 45.000000
 38.000000 48.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 38.000000 13.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000

 13.000000 27.000000 13.000000 38.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000

 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000

ソート完了
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000

うまくいったな。
改良できそうな部分もあるけどめんどいからほっとこうｗ