| 『分割すべき配列の要素数が３以上であれば、先頭の要素、中央の要素、末尾の要素の三値の中央値をもつ要素を枢軸として選択する。』というアイディアに基づいて枢軸を選択する方針を用いて、List 6-9の関数quick を書きかえよ。 |
/* 演習6-10 クイックソート */ #include <stdio.h> #define swap(type, x, y) do { type t = x; x = y; y = t; } while (0) /*--- a, b, cの中央値を求める ---*/ int med3(int a, int b, int c) { if (a > b) return (a <= c ? a : b > c ? b : c); else return (b <= c ? b : a > c ? a : c); } /*--- クイックソート ---*/ void quick(int a[], int left, int right) { int pl = left; /* 左カーソル */ int pr = right; /* 右カーソル */ int x = (pr - pl < 2) ? a[pl] /* 枢軸 */ : med3(a[pl], a[(pl + pr)/2], a[pr]); do { while (a[pl] < x) pl++; while (a[pr] > x) pr--; if (pl <= pr) { swap(int, a[pl], a[pr]); pl++; pr--; } } while (pl <= pr); if (left < pr) quick(a, left, pr); if (pl < right) quick(a, pl, right); } int main(void) { int i; int x[9]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力せよ。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d] : ", i); scanf("%d", &x[i]); } quick(x, 0, nx - 1); /* 配列xをクイックソート */ puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }
