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

戻る  

演習6-15の解答

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

戻る