C言語アルゴリズム-クイックソート



クイックソート(quick sort)とは

クイックソート(quick sort)

クイックソートとは、1962年にCharles Antony.A.R.Hoareが発表した、分割統治アプローチ(大きな問題を複数の小さな問題に分割して各個解決する)の整列アルゴリズムです。基準とする要素より小さい要素グループと大きい要素グループに分割する作業を繰り返すことで整列を行います。

クイックソートの処理の流れは以下の通りです。

  1. ある一つの適当な要素を選び出し、最終的に置かれるべき位置へ移動する。この要素を「枢軸(pivot)」と呼ぶ。
  2. 枢軸より大きな要素は右側へ、小さな要素は左側に置き、2つの部分配列を作成(partition)する。
  3. 部分配列がただ1つの要素になるまで、クイックソートのアルゴリズムを適用して分割を繰り返す。

以上、全ての分割が終るとソートが完了しています。


クイックソートの整列過程

[before]:6 1 4 2 3 7 5 
---------[1 round]---------
[array]:6 1 4 2 3 7 5 
[pivot] = 5
[swap] (left=6) <-> (right=5)
[array]:(5 1 4 2 3) (7 6)
---------[2 round]---------
[array]:5 1 4 2 3
[pivot] = 4
[swap] (left=5) <-> (right=3)
[swap] (left=4) <-> (right=2)
[array]:(3 1 2) (4 5)
---------[3 round]---------
[array]:3 1 2
[pivot] = 2
[swap] (left=3) <-> (right=2)
[array]:(2 1) (3) 
---------[4 round]---------
[array]:2 1
[pivot] = 2
[swap] (left=2) <-> (right=1)
[array]:(1) (2)
---------[5 round]--------- 
[array]:(4 5)
[pivot] = 4
[swap] (left=4) <-> (right=4)
[array]:(4) (5) 
---------[6 round]---------
[array]:(7 6)
[pivot] = 7
[swap] (left=7) <-> (right=6)
[array]:(6) (7) 
==============================
[after] :1 2 3 4 5 6 7 

クイックソートの性能

クイックソートは内部整列では最速のアルゴリズムといわれており、平均計算量が「O(n log n)」です。しかし、ピボットの選択を間違えた場合などはバブルソートと同等の処理内容になってしまうため、最悪計算量が「O(n ^ 2)」となります。要素が少ない場合には、クイックソートよりも選択ソートの方が速いこともあります。


ピボットの選択

ピボットの選択を間違えた場合、計算量は最悪の「O(n ^ 2)」となります。

効率の悪いピボットを選ぶ可能性を排除するため、配列から3つほどデータを取り出して、その中央値をピボットに選ぶという「median-of-three」という手法がよく用いられます。


qsort()関数について

標準ライブラリにはqsort()関数がクイックソートを行う処理として用意されています。自作してバグを内臓するよりは、まずはqsort()を用いることができるかどうか検討したほうが賢明です。


C言語によるクイックソートのプログラム

再起処理で実装したクイックソートは実装が簡単ですが、データ量が多い場合にスタック不足でエラーとなることがあります。そのような場合には、スタックを用いて非再起処理のクイックソートを実装するなどの工夫を行う必要があります。

非再起版のクイックソートと再起版のクイックソートを以下に記述します。

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

#define STACK_SIZE 32

/*!
 * @brief       配列にランダムな数値を格納する。
 * @param[out]  array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_random_number(int *array, unsigned int size)
{
    int i;

    /* 起動毎に異なる乱数を発生させる */
    srand((unsigned int)time(NULL));
    for(i = 0; i < size; i++){
        array[i]=rand();
    }
}

/*!
 * @brief       配列内容を表示する
 * @param[in]   array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_print(int *array, unsigned int size)
{
    int i = 0;

    for(i = 0; i < size; i++){
        printf("%d ", array[i] );
    }
    putchar('\n');
}

/*!
 * @brief      要素要素を入れ替える
 * @param[in]  i  要素位置
 * @param[in]  j  要素位置
 */
static void
swap(int *i, int *j)
{
    int temp;

    temp = *i;
    *i   = *j;
    *j   = temp;
}

/*!
 * @brief          枢軸の値を取得する。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      left   配列の左端
 * @param[in]      right  配列の右端
 * @return         枢軸の添え字
 * @note           左端、中央、右端の中央値を枢軸とする。
 */
static int
get_pivot(int array[], int left, int right)
{
    int x, y, z;
    int center = (right + left) / 2;

    x = array[center];
    y = array[left];
    z = array[right];

    if((x <= y && y <= z)||(z <= y && y <= x)) return(y);
    if((x <= z && z <= y)||(y <= z && z <= x)) return(z);
    return(x);
}

/*!
 * @brief          配列を分割する
 * @param[in/out]  array  整列する要素配列
 * @param[in]      left   配列の左端
 * @param[in]      right  配列の右端
 * @return         分割位置
 */
static int
partition(int array[], int left, int right)
{
    int pivot_val;

    /* 枢軸の値を取得する */
    pivot_val = get_pivot(array, left, right);

    while(left <= right){
        /* 枢軸より大きな要素が見つかるまでポインタを右へ進める */
        while(array[left]  < pivot_val) left++;

        /* 枢軸より小さな要素が見つかるまでポインタを左へ進める */
        while(array[right] > pivot_val) right--;

        /* 要素を交換する */
        if(left <= right){
            swap(&array[left], &array[right]);
            left++;
            right--;
        }
    }

    return(left);
}

/*!
 * @brief          再帰処理でクイックソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
recursive_quick_sort(int array[], unsigned int size)
{
    int pivot = 0;
    int left  = 0;
    int right = size - 1;

    /* 部分配列がただ一つになれば処理を終了する */
    if(size <= 1) return;
  
    /* 枢軸を基準として分割する */
    pivot = partition(array, left, right);

    /* 左右の部分配列をそれぞれクイックソートする */
    recursive_quick_sort(array, pivot);
    recursive_quick_sort(array + pivot, size - pivot);
}

/*!
 * @brief          クイックソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
quick_sort(int array[], unsigned int size)
{
    int pivot;
    int left, right;
    int low_stack[STACK_SIZE];
    int high_stack[STACK_SIZE];
    int sp = 1;  /* スタックポインタ */

    /* スタックを初期化する */
    low_stack[0]  = 0;
    high_stack[0] = size - 1;
  
    while(sp > 0){
        /* スタックから整列する範囲の添字を取り出す */
        sp--;
        left  = low_stack[sp];
        right = high_stack[sp];

        if(left < right){
            /* 枢軸を基準として分割する */
            pivot = partition(array, left, right);

            /* 右側の部分配列位置をスタックに記憶する */
            low_stack[sp]  = pivot;
            high_stack[sp] = right;
            sp++;

            /* 左側の部分配列位置をスタックに記憶する */
            low_stack[sp]  = left;
            high_stack[sp] = pivot - 1;
            sp++; 
        }
    }
}

int
main(void)
{
    //int buf[] = {9,4,2,3,8,5,1,10,0,7,6};
    int buf[1000];
    array_random_number(buf, sizeof(buf)/4);

    printf("[before]:"); array_print(buf, (sizeof(buf)/4));

    quick_sort(buf, (sizeof(buf)/4));

    printf("[after] :"); array_print(buf, (sizeof(buf)/4));

    return( 0 );
}

関連ページ



スポンサード リンク