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

戻る  

演習6-11の解答

/*
    演習6-11
    クイックソート（非再帰版）
*/

#include  <stdio.h>

#define swap(type, x, y)    do { type t = x; x = y; y = t; } while (0)

/*--- クイックソート（非再帰版） ---*/
void quick(int a[], int left, int right)
{
    int  ptr = 0;               /* スタックポインタ */
    int  lstack[100];           /* 分割すべき先頭要素の添字のスタック */
    int  rstack[100];           /* 分割すべき末尾要素の添字のスタック */

    lstack[ptr] = left;
    rstack[ptr] = right;
    ptr++;

    while (ptr-- > 0) {
        int  pl = left  = lstack[ptr];      /* 左カーソル */
        int  pr = right = rstack[ptr];      /* 右カーソル */
        int  x = a[(left + right) / 2];     /* 枢軸は中央の要素 */

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) {
                swap(int, a[pl], a[pr]);
                pl++;
                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++;                          /* プッシュする　　 */
        }
        if (pl < right) {
            lstack[ptr] = pl;               /* 末尾側のグループ */
            rstack[ptr] = right;            /* の範囲（添字）を */
            ptr++;                          /* プッシュする　　 */
        }
    }
}

int main(void)
{
    int  i;
    int  x[8];
    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, 0, nx - 1);                    /* 配列xをクイックソート */

    puts("昇順にソートしました。");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);

    return (0);
}

戻る