サイトマップ / C言語講座>出入り口>総目次>目次:ソート>クイックソート
/* 今日は一連のソートのアルゴリズムの学習の総仕上げとして、クイックソートについて学びます。クイックソートは、名前の通り高速なソートです。クイックソートのアルゴリズムについて説明します。
int 型の配列 x[ ] をソートするとします。 配列の中央付近の要素の値を基準にします。 配列の添字の小さい方から基準値に向かって、 基準値より大きい値を探します。 配列の添字の大きい方から基準値に向かって、 基準値より小さい値を探します。 見つかったら、双方を交換します。 これを両者が衝突するまで行います。 その結果基準値より小さな値が、基準値の左に、大きな値が右にきます。 次いで、基準値の左の配列と右の配列に対して、同じ操作をします。 配列の要素が 1 になるまで、上記の操作を行えば、ソートが完了します。
具体例を下記に示します。
下記の配列で、中央の要素の値 52 を基準値にします。 22 63 48 69 52 13 84 98 32 63 は 52 より大きく、32 は 52 より小さいので、交換します。 22 63 48 69 52 13 84 98 32 交換した結果です。 22 32 48 69 52 13 84 98 63 69 は 52 より大きく、13 は 52 より小さいので、交換します。 22 32 48 69 52 13 84 98 63 交換した結果、52 より小さい値が 52 の左に、大きい値が右にきます。 22 32 48 13 52 69 84 98 63 52 の左右の部分配列に対して、同様な操作を要素が 1 になるまで繰り返します。
*/
#include <stdio.h> void QSort(int x[ ], int left, int right); void Swap(int x[ ], int i, int j); void ShowData(int x[ ], int n); void main(void); /* クイックソートを行う */ void QSort(int x[ ], int left, int right) { int i, j; int pivot; i = left; /* ソートする配列の一番小さい要素の添字 */ j = right; /* ソートする配列の一番大きい要素の添字 */ pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */ while (1) { /* 無限ループ */ while (x[i] < pivot) /* pivot より大きい値が */ i++; /* 出るまで i を増加させる */ while (pivot < x[j]) /* pivot より小さい値が */ j--; /* 出るまで j を減少させる */ if (i >= j) /* i >= j なら */ break; /* 無限ループから抜ける */ Swap(x, i, j); /* x[i] と x[j]を交換 */ i++; /* 次のデータ */ j--; } ShowData(x, 10); /* 途中経過を表示 */ if (left < i - 1) /* 基準値の左に 2 以上要素があれば */ QSort(x, left, i - 1); /* 左の配列を Q ソートする */ if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */ QSort(x, j + 1, right); /* 右の配列を Q ソートする */ } /* 配列の要素を交換する */ void Swap(int x[ ], int i, int j) { int temp; temp = x[i]; x[i] = x[j]; x[j] = temp; } /* n 個のデータを表示する */ void ShowData(int x[ ], int n) { int i; for (i = 0; i < n ; i++) printf("%d ", x[i]); printf("\n"); } void main(void) { /* ソートする配列 */ int x[ ] = {6, 3, 1, 7, 0, 4, 8, 5, 2, 9}; int n = 10; printf("ソート前:\n"); ShowData(x, n); printf("ソート中:\n"); QSort(x, 0, n - 1); printf("ソート後:\n"); ShowData(x, n); } |
/* 今回はあくまで学習ということで、要素数 10 の配列をソートしました。配列の要素数が少ない時は、他のソートの方が適しています。
標準ライブラリ関数に qsort( ) があります。今回のソースプログラムは、プリミティブなものです。ライブラリ関数は、さらに高速にソートできるように改良されています。実用のプログラムではそちらを使って下さい。 */
/* (C) 2000- YFプロ. All Rights Reserved. */ 提供:C言語講座−それ自体コンパイルできる教材を使った講座です−