さまざまなソートのアルゴリズムを、 プログラムを書きながら学んでいるとしよう。 その場合、とりあえずは、 100 未満の自然数に値をもつ乱数で初期化された配列をソートする、 といった程度のプログラムを書けば十分であろう。
その際、配列全体を
03 14 15 92 65 35 89 79 32 38 46 26 43のように印字する関数を書いておき、 これを適当なところで呼び出すようにすると、 debug の役に立つし、 途中経過がわかるのでアルゴリズムの理解の手助けにもなる。
配列の一つの要素につき 3 文字分のスペースを要するから、 コンソールの横幅が 120 カラムとすると、配列の大きさは 40 程度。 これで十分なのだが、
まずは色を選ぼう。同じ色だが、 左は「＃」を、右は色を表わす番号を表示してみた。
＃ ＃ ＃ ＃ ＃ ＃ ＃ ＃ ＃ ＃ ＃ ＃ |
ff0000
ff00aa ffaa00
ff00ff ffff00
aa00ff aaff00
0000ff 00ff00
00aaff 00ffaa
00ffff
|
この十二色から、 １０時と１１時の位置にある二色を除いた十色を用いて表示するようにしてみた。 クイックソートと組み合わせたプログラム例を下に示す。 配列の大きさは 100 とし、 それを 0 から 99 までの整数が一度ずつ現れるように初期化した。
/******************************************************************************
0 ... 99 をシャッフルして得られた配列 a[ ] をクイックソートする。
表示は、十位は色で、一位は数字で。黒地の html ファイルを吐く。
******************************************************************************/
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
#define N 100
void init(void);
void print(void);
void quicksort(int i, int j);
void swap(int i, int j);
int a[N];
int main() {
printf("<html>\n"); /* html の最初の部分。略式 :-) */
printf("<body bgcolor=\"black\">\n");
printf("<p>\n");
printf("<pre>\n");
init();
print();
quicksort(0, N-1);
printf("</pre>\n"); /* html の最後の部分。略式 :-) */
printf("</p>\n");
printf("</body>\n");
printf("</html>\n");
return 0;
}
void init(void) {
int i;
for (i = 0; i < N; i++) {
a[i] = i;
}
srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */
for (i = N-1; i > 0; i--) { /* シャッフルする */
swap(i, rand() % (i+1));
}
return;
}
/* 配列 a[0] ... a[N-1] を印字。十位は色で、一位は数字で表示される */
void print(void) {
int i;
for (i = 0; i < N; i++) {
if (i > 0 && a[i] / 10 == a[i-1] / 10) { /* 一つ手前と同色のとき */
printf("%d", a[i] % 10);
} else { /* そうでないとき */
printf("<font color=\"");
switch(a[i] / 10) {
case 0: printf("#ff0000"); break; /* 赤 */
case 1: printf("#ff8800"); break;
case 2: printf("#ffff00"); break; /* 黄 */
case 3: printf("#88ff00"); break;
case 4: printf("#00ff00"); break; /* 緑 */
case 5: printf("#00ff88"); break;
case 6: printf("#00ffff"); break; /* シアン */
case 7: printf("#0088ff"); break;
case 8: printf("#0000ff"); break; /* 青 */
case 9: printf("#8800ff"); break;
default: ;
}
printf("\">%d", a[i] % 10);
}
if (i == N-1 || a[i] / 10 != a[i+1] / 10) { /* 次が違う色のとき */
printf("</font>");
}
}
printf("\n");
}
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) {
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);
print();
quicksort(left, i-1);
quicksort(i+1, right);
}
上のプログラムでは、 再帰呼び出しの直前に印字関数を呼んでいる。 全く同じ行が二回続けて出力されることがあるが、 それは前々項に書いた「間に合わせ版 uniq」で取り除けばよい。 また、pivot としては左端の元を選んでいる。
出力例を次に示す。
5187401274681271323444986859306904303908753072658196102447166987108510222382769397437246165358905595 2190401571681641323444989357326322005788956705658196172440163709108313402980969867437272465328975585 1890751023462841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 6890751023412841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 1430256079812841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 0134256079812841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 0123456079812841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 0123456879012841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 0123456789012841323644989357126327500481956705658196172440163709108313402980969867437272465328975585 0123456789012168323644905757826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012468573091465237826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012348576091465237826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012346578091465237826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012345678091465237826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012345678901465237826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012345678901234567826323908411954705658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890123208431954765658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890127208631954345658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890126453781902345658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890123456781902345658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890123456780912345658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890123456789012345658196172440163709108313402980969867437272465328975585 0123456789012345678901234567890123456789012345758196572450163709108315402782969836434262775608993481 0123456789012345678901234567890123456789012345024366819757163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345679806314257163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345678906314257163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345678905314267163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345678902314567163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345678901234567163402108375402752999816834562775608993481 0123456789012345678901234567890123456789012345678901234567763408108995212054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567963425108798012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567893425106798012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567891023546798012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567890123546798012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456798012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012054739816234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012654739801234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012354679801234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012345679801234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234562775608993481 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234560718928963457 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234568790128963457 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890128963457 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890125763489 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 |
2006-03-19 (0) 01:04:33 +0900