クイックソートの練習
最近プログラミングをやってなかったので、少し腕が落ちてきたかなとか思ってしまったので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; }