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

戻る  

演習6-14の解答

/*
    演習6-14
    クイックソート（汎用版）
*/

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>

/*--- 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 *))
{
    if (nmemb > 0) {
        size_t  pl = 0;                 /* 左カーソル */
        size_t  pr = nmemb - 1;         /* 右カーソル */
        size_t  pv = nmemb;             /* ピボット */
        size_t  pt = (pl + pr) / 2;     /* ピボットの更新値 */
        char    *v = (char *)base;      /* 先頭要素へのポインタ */
        char    *x;                     /* ピボットへのポインタ */

        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 (0  < pr)      quick(&v[0],         pr + 1,     size, compar);
    QuickRight:
        if (pl < nmemb-1) quick(&v[pl * size], nmemb - pl, size, compar);
    }
}

/*--- 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);
}

戻る