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

演習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);
}

戻る