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

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

だいたい先頭、だいたい最後のクイックソート。

スポンサーリンク

クイックソートの勉強をしてみた。
クイックソートのアルゴリズムは以下の通り。

①ある適当な数字を決めて、それよりも大きいものは後ろへ、小さいものは前へ移動
② ①の時点で、「①で選んだ数字より大きいグループ」と「①で選んだ数字より小さいグループ」の2つに別れるので、それぞれのグループの中で適当な数字を選んで、大きいものは前へ、小さいものは後ろへ持っていく。
③ ①、②の処理を繰り返す。
④もうこれ以上グループ分けできない!となったら終了。

Excelで表すとこんな感じ。

コードはこんな感じである。

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

#define		N	10 /*データ件数 */

int sort[N];

void QuickSort(int bottom, int top, int *data) {
	int lower, upper, div, temp;
	if (bottom >= top) {
		return;
	}

	div = data[bottom];
	for  (lower = bottom, upper = top; lower < upper;) {
		while (lower <= upper && data[lower] <= div) {
			lower++;
		}
		while(lower <= upper && data[upper] > div) {
			upper--;
		}
		if (lower < upper) {
			temp = data[lower];
			data[lower] = data[upper];
			data[upper] = temp;
		}
	}
	temp = data[bottom];
	data[bottom] = data[upper];
	data[upper] = temp;

	QuickSort(bottom, upper -1, data);
	QuickSort(upper + 1, top, data);
}

int main(void) {
	int i;
	srand((unsigned int) time(NULL));
	printf("before:\n");

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

	printf("\nstart:\n");
	QuickSort(0, N -1 , sort);

	printf("\nfinish:\n");

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

結果

before:
27168 11934 31396 14973 32223 7910 24190 19227 2244 29755 
start:

finish:
2244 7910 11934 14973 19227 24190 27168 29755 31396 32223 [Finished in 0.1s]

参考にしまくった本

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

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


本当にわかりやすいし、C++の勉強にもなる。
アルゴリズム本のバイブルだと思う。

感謝のプログラミング

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