BohYoh.comトップページへ

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

戻る  

演習6-12の解答(その1)

 クイックソートは、要素数が小さい場合は、それほど高速ではないことが知られている。そこで、分割された配列の要素数が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); }


戻る