BohYoh.comトップページへ

C言語によるアルゴリズムとデータ構造

戻る  

演習6-15の解答

 qsort 関数と同じ形式で呼び出すことのできる以下の関数を作成せよ。
  void quick (void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *));

クイックソートのアルゴリズムを用い、再帰呼出しを用いずに実現すること。

/* 演習6-15 クイックソート(汎用・非再帰版) */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define swap(type, x, y) do { type t = x; x = y; y = t; } while (0) /*--- x, yの指すnバイトの領域を交換 ---*/ void memswap(void *x, void *y, size_t n) { unsigned char *a = (unsigned char *)x; unsigned char *b = (unsigned char *)y; for ( ; n--; a++, b++) { unsigned char c = *a; *a = *b; *b = c; } } /*--- クイックソート(非再帰版) ---*/ void quick(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t ptr = 0; /* スタックポインタ */ size_t lstack[100]; /* 分割すべき先頭要素の添字のスタック */ size_t rstack[100]; /* 分割すべき末尾要素の添字のスタック */ char *v = (char *)base; char *x; /* ピボットへのポインタ */ if (nmemb == 0) return; lstack[ptr] = 0; rstack[ptr] = nmemb - 1; ptr++; while (ptr-- > 0) { size_t left = lstack[ptr]; size_t right = rstack[ptr]; size_t pl = left; /* 左カーソル */ size_t pr = right; /* 右カーソル */ size_t pv = nmemb; /* ピボット */ size_t pt = (pl + pr) / 2; /* ピボットの更新値 */ do { if (pv != pt) x = &v[(pv = pt) * size]; while (compar((const void*)&v[pl * size], x) < 0) pl++; while (compar((const void*)&v[pr * size], x) > 0) pr--; if (pl <= pr) { pt = (pl == pv) ? pr : (pr == pv) ? pl : pv; memswap(&v[pl * size], &v[pr * size], size); pl++; if (pr == 0) /* 符号無し整数0からのデクリメントを避ける */ goto QuickRight; pr--; } } while (pl <= pr); if (pr - left < right - pl) { swap(int, left, pl); swap(int, right, pr); } if (left < pr) { lstack[ptr] = left; /* 先頭側のグループ */ rstack[ptr] = pr; /* の範囲(添字)を */ ptr++; /* プッシュする   */ } QuickRight: if (pl < right) { lstack[ptr] = pl; /* 末尾側のグループ */ rstack[ptr] = right; /* の範囲(添字)を */ ptr++; /* プッシュする   */ } } } /*--- int型の比較関数(昇順ソート用) ---*/ int int_cmp(const int *a, const int *b) { if (*a > *b) return (1); else if (*a < *b) return (-1); else return (0); } int main(void) { int i; int x[7]; 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, /* 配列 */ nx, /* 要素数 */ sizeof(int), /* 要素の大きさ */ (int (*)(const void *, const void *))int_cmp /* 比較関数 */ ); puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }


戻る