クイックソートを説明する際、
しかし、実際に書く再帰を用いたプログラムでは、 分割はこういうふうには進まない。 そのことは、 《ソートの過程を「色＋数字」で表示する》、 《ソートの過程を色で表示する》、 《ソートの過程を色で表示する（table 版）》 を見てもわかる。
上のように“見せる”ためには、再帰をやめ、次のようにすればよいのではないか。 クイックソートの各段階では pivot と呼ばれる要素を選ぶが、 その段階の終了時にその要素が収まる位置は、 最後にその要素が収まるべき位置であることに注意する。 ソートすべき配列と同じ大きさの char の配列をとり、 すべてに「未確定」を示す値を入れておく。 クイックソートの本質的部分となる関数からは、最後の再帰呼び出しを除いておく。 最初に配列全体に対しその関数を適用したら、pivot の収まった位置は「確定」とする。 次は、「配列の最初からいま確定した要素の手前まで」と 「いま確定した要素の次から配列の最後まで」にその関数を適用し、 pivot の収まった位置 --- 二箇所ある --- を「確定」とする。 次は三箇所の「確定」で区切られた四つの部分にその関数を適用する。---
（pivot の収まる位置によっては適用される区間が 2 のベキ乗個に分かれないこともある。）
プログラムは以下の通り。
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
#define COLOR
#ifdef COLOR
#define N 100
#else
#define N 26
#endif
void init(void);
void print(void);
#ifdef COLOR
void printincolor(int i);
#endif
void quicksort(int i, int j);
void swap(int i, int j);
int find(int i, const int k);
int a[N]; /* ソートされる配列 */
char c[N]; /* 確定済みかどうかのフラグ。0 は未確定、1 は確定 */
int main() {
int i, j;
#ifdef COLOR
printf("<html>\n"); /* html の最初の部分。略式 :-) */
printf("<body>\n");
printf("<p>\n");
printf("<table border=\"1\" cellspacing=\"0\">\n");
#endif
init();
print();
while ((i = find(0, 0)) != N) { /* 未確定がある限り */
do {
j = find(i, 1) - 1; /* その未確定ブロックの右端を探して */
quicksort(i, j); /* その間を“クイックソート” */
} while ((i = find(j + 1, 0)) != N); /* 次を探し、見つかる限り */
print();
}
#ifdef COLOR
printf("</table>\n");
printf("</p>\n"); /* html の最後の部分。略式 :-) */
printf("</body>\n");
printf("</html>\n");
#endif
return 0;
}
void init(void) {
int i;
for (i = 0; i < N; i++) {
a[i] = i; c[i] = 0;
}
srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */
for (i = N-1; i > 0; i--) { /* シャッフルする */
swap(i, rand() % (i+1));
}
return;
}
#ifndef COLOR
void print(void) {
int i;
for (i = 0; i < N; i++) {
printf(" %02d", a[i]);
}
printf("\n");
for (i = 0; i < N; i++) {
printf(" %c", c[i] ? '|' : ' ');
}
printf("\n");
}
#else
void print(void) {
int i;
printf("<tr>\n");
for (i = 0; i < N; i++) {
printincolor(i);
}
printf("</tr>\n");
printf("<tr>\n");
for (i = 0; i < N; i++) {
if (c[i] == 0) {
printf("<td bgcolor=\"black\"> </td>\n");
} else {
printincolor(i);
}
}
printf("</tr>\n");
}
/* a[i] を色で表示。<td bgcolor="#0fffff"> </td> のように。*/
void printincolor(int i) {
printf("<td bgcolor=\"");
switch(a[i] / 20) {
case 0: printf("#ff%02x0f", 15 + a[i] % 20 * 12); break;
case 1: printf("#%02xff0f", 255 - a[i] % 20 * 12); break;
case 2: printf("#0fff%02x", 15 + a[i] % 20 * 12); break;
case 3: printf("#0f%02xff", 255 - a[i] % 20 * 12); break;
case 4: printf("#%02x0fff", 15 + a[i] % 20 * 12); break;
default: ;
}
printf("\"> </td>\n");
}
#endif
void swap(int i, int j) {
int tmp;
tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
/* ↓あまりしっかりチェックしていないのでミスがあるかも */
void quicksort(int left, int right) {
int i, j;
int pivot;
if (left == right) {
c[left] = 1; return;
}
pivot = a[left];
i = left;
j = right;
while (i < j) {
while (i <= right && a[i] <= pivot) {
i++;
}
while (j >= left && a[j] >= pivot) {
j--;
}
if (i < j) {
swap(i, j); i++; j--;
}
}
/* ここへきたときは i == j または i == j + 1 になっている */
if (i != j || a[i] > pivot) {
i--;
}
swap(left, i);
c[i] = 1;
}
/* i 以上で最初に c[i] == k となる i を返す。見つからなければ N を返す */
int find(int i, const int k) {
while (i < N && c[i] != k) {
i++;
}
return i;
}
「#define COLOR」を消すと次のような出力が得られる。 下に「|」が書かれた要素は確定している。
16 19 21 15 24 08 17 18 10 20 12 13 25 23 01 00 11 02 09 06 22 14 03 04 07 05
11 05 07 15 04 08 03 14 10 06 12 13 09 02 01 00 16 23 25 20 22 18 17 24 21 19
|
09 05 07 00 04 08 03 01 10 06 02 11 13 12 14 15 16 21 19 20 22 18 17 23 24 25
| | |
06 05 07 00 04 08 03 01 02 09 10 11 12 13 14 15 16 18 19 20 17 21 22 23 24 25
| | | | | | |
03 05 02 00 04 01 06 08 07 09 10 11 12 13 14 15 16 17 18 20 19 21 22 23 24 25
| | | | | | | | | | | | | |
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| | | | | | | | | | | | | | | | | | |
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| | | | | | | | | | | | | | | | | | | | | | |
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| | | | | | | | | | | | | | | | | | | | | | | | |
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| | | | | | | | | | | | | | | | | | | | | | | | | |
上のままだと以下のような出力になる。 奇数行目は配列の値を対応する色で示したもの。 偶数行目には、未確定は黒で、確定はその上のマスと同じ色で表示されている。 （色の対応については 《ソートの過程を色で表示する》 を参照。）
2006-03-27 (1) 02:04:39 +0900