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

戻る  

演習6-12の解答（その２）

/*
    演習6-12
    クイックソート（要素数9以下は単純挿入ソート：非再帰版）
*/

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

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

/*--- 単純挿入ソート ---*/
void insertion(int a[], int n)
{
    int  i, j;

    for (i = 1; i < n; i++) {
        int  tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

/*--- クイックソート（非再帰版） ---*/
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];     /* 枢軸は中央の要素 */

        if (right - left <= 9)
            insertion(&a[left], right - left + 1);
        else {
            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[50];
    int  nx = sizeof(x) / sizeof(x[0]);

    srand((unsigned)time(NULL) % RAND_MAX);

    printf("配列の要素の値は以下のとおりです\n", nx);
    for (i = 0; i < nx; i++) {
        x[i] = rand() % 1000;
        printf("x[%d] = %d\n", i, 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);
}

戻る