サイトマップ / 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言語講座−それ自体コンパイルできる教材を使った講座です−

青い直線

サイトマップ / C言語講座出入り口総目次目次:ソート>クイックソート