クイックソートの練習

最近プログラミングをやってなかったので、少し腕が落ちてきたかなとか思ってしまったのでK&Rを引っ張り出してプログラミングの練習をやってみる。それにしてもクイックソートは1960年代に考案されたと言うから、計算機科学の歴史の重みというのを感じる。コンピュータに関する学問はまだまだ若くて未熟だと思うけれども、コンパイラ理論とかはもう枯れてしまっている。

/*   クイックソートの簡単なプログラム 
 *   K&R 106p
 *   2006年2月11日
 */
#include <stdio.h>
#define NUMBER(arr) (size_t)(sizeof(arr)/sizeof(arr[0]))

/* swap(): 配列の要素を交換する */
void swap(int v[], int i, int j)
{
	int temp = v[i]; v[i] = v[j]; v[j] = temp;
	
	return;
}

/* qsort(): 配列の要素をクイックソートをする */
void qsort(int v[], int left, int right)
{
	int i, last;
	void swap(int v[], int i, int j);
	
	if (left >= right) {
		return;
	}
	swap(v, left, (left+right)/2);
	last = left;
	for (i = left+1; i<= right; i++) {
		if (v[i] < v[left]) {
			swap(v, ++last, i);
		}
	}
	
	swap(v, left, last);
	qsort(v, left, last-1);
	qsort(v, last+1, right);
}

int main(void)
{
	int i;
	
	/* ソート対象の配列データ */
	int arr[] = { 34, 38, 15, 35, 14, 24, 32, 21, 20, 42, 36, 23 };
	
	for (i = 0; i < NUMBER(arr); i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	qsort(arr, 0, NUMBER(arr) - 1);
	
	for (i = 0; i < NUMBER(arr); i++) {
		printf("%d ", arr[i]);
	}
	
	return 0;
}