感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

効率が悪いバブルソート。

<スポンサーリンク>

ことば

非効率なソフトウェアが醜いのではない。醜いのは、プログラマに不要な仕事をさせる言語だ。
本当の非効率性とは、マシンの時間を無駄にすることではなく、プログラマの時間を無駄にすることだ。コンピュータが速くなればなるほど、このことははっきりしてくる。
ハッカーと画家 コンピュータ時代の創造者たち「百年の言語」より

環境構築

■C,C++のコンパイル環境を構築(GCC)
・インストーラーをダウンロードして実行するだけ
http://sourceforge.net/projects/mingw/files/
C++コンパイラもチェックボックスにチェックしてインストールしておくといいと思う。

今はVisual Stadioがいいのかもしれなけれど、より原始的な環境でコンパイルすることで、
ちゃんと関数などを覚えることができるかと思っている。

・システムの環境変数にインストールフォルダ(デフォルトはC:\MinGW\bin)のパスを通しておく

アルゴリズムとデータ構造

バブルソート
バブルソートって何?
先頭から順に見ていって、左右でおかしいところを並べ替える。
最後までいったらまた先頭から見ていく。
一回も並び替えが無く最後まで見終わったらソート完了!

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

#define		N	80000 

int		sort[N];

void BubbleSort(void) {
	int i, j, flag;

	do {
		flag = 0;
		for(i = 0; i < N - 1; i++) {
			if(sort[i] > sort[i + 1]) {
				flag = 1;
				j = sort[i];
				sort[i] = sort[i + 1];
				sort[i + 1] = j;
			}
		}
	} while(flag == 1);

}

int main(void) {
	int i;

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

	printf("Preparation:\n");
	for (i = 0; i < N; i++) {
		sort[i] = rand();
		printf("%d ", sort[i]);
	}
	printf("\n Begin:\n");
	BubbleSort();

	printf("\nFinished:\n");

	for (i = 0; i < N; i++) {
		printf("%d ",sort[i]);
	}

	return EXIT_SUCCESS;
}

バブルソートは、「ループが1回終了すると、後方の要素は確実にソート済みになっている。
なので、繰り返すごとに、比較する配列末尾のインデックスの数を減らすことで、繰り返しの数を半分に減らすことができる。

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

#define		N	80000

int		sort[N];

void BubbleSort2(void) {
	int i, j, flag, k;

	k = 0;
	do {
		flag = 0;
		for (i = 0; i < N - 1 - k; i++) {
			if(sort[i] > sort[i + 1]) {
				flag = 1;
				j = sort[i];
				sort[i] = sort[i + 1];
				sort[i + 1] = j;
			}
		}
		k++;
	} while(flag == 1);

}

int main(void) {
	int i;

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

	printf("Preparation:\n");
	for (i = 0; i < N; i++) {
		sort[i] = rand();
		printf("%d ", sort[i]);
	}
	printf("\n Begin:\n");
	BubbleSort2();

	printf("\nFinished:\n");

	for (i = 0; i < N; i++) {
		printf("%d ",sort[i]);
	}

	return EXIT_SUCCESS;
}

今日読んだ本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


1時間でゲームを作った動画がすごすぎて、感動して思わずこの購入してしまった。
C言語とかほとんどやったことないけれど、すごく勉強になる。本に無駄がない気がする。
サンプルをほとんど真似してばっかりだったから、次からはちゃんと自分なりに改造してサンプルとしたい。

感謝のプログラミング

今回で感謝のプログラミングは【230時間目】
10000時間まで、あと【9770時間】