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

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

　クイックソートは、要素数が小さい場合は、それほど高速ではないことが知られている。そこで、分割された配列の要素数が9以下であれば、単純挿入ソートを行うように切りかえるプログラムを作成せよ。
　なお、再帰版と非再帰版の両方を作成すること。

/*
    演習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  pl = left;         /* 左カーソル */
    int  pr = right;        /* 右カーソル */
    int  x = a[(pl+pr)/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 (left < pr)  quick(a, left, pr);
        if (pl < right) quick(a, pl, right);
    }
}

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

戻る