BohYoh.comトップページへ

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

戻る  

演習6-16の解答

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

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

/* 演習6-16 シェルソート(汎用版) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define swap(type, x, y) do { type t = x; x = y; y = t; } while (0) /*--- シェルソート(汎用版) ---*/ void shell(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t i, j, h; char *v = (char *)base; char *temp = malloc(size); if (temp == NULL) return; for (h = 1; h < nmemb / 9; h = h * 3 + 1) ; for ( ; h > 0; h /= 3) for (i = h; i < nmemb; i++) { memcpy(temp, &v[i * size], size); for (j = i - h; compar((const void*)&v[j * size], temp) > 0; j -= h) { memcpy(&v[(j + h) * size], &v[j * size], size); if (j < h) /* 符号無し整数がマイナスにならないように */ goto Ex; } j += h; Ex: memcpy(&v[j * size], temp, size); } free(temp); } /*--- 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]); } shell(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); }


戻る