クイックソート | Programming Place Plus　アルゴリズムとデータ構造編【整列アルゴリズム】　第６章

トップページ – アルゴリズムとデータ構造編

この章の概要 🔗

この章の概要です。


クイックソート 🔗

この章では、クイックソートを取り上げます。

クイックソートは、その名のとおり、非常に高速なソートを実現するアルゴリズムです。

具体的には、平均計算量が O(n log n)であり、対象のデータ列に事前に何らかの制約を要求しない汎用的なソートアルゴリズムとしては理論上、最高性能となります。

しかし、クイックソートの最悪時の計算量は O(n2)です。これはバブルソート📘（第３章）などの遅いソートアルゴリズムと同等です。

このように性能のふり幅がとても大きいのですが、最悪のケースは、実装を工夫することでほぼ避けられます。この辺りのことは、後程説明します。


クイックソートの原理は次のようになります。まず、対象のデータ列の中から、適当な１つの要素を選択します。この要素を基準値（ピボット）といいます。

そして、データ列を、基準値より小さい要素と大きい要素とに分割していきます。

結果、データ列の先頭付近には基準値より小さい値を持った要素が集まり（まだソートはされていません）、その次に基準値となった要素が来て、さらにその後ろには、基準値より大きい値を持った要素が集まります（こちらもまだソートはされていません）。

たとえば、元のデータ列が次のようになっているとします。

{7, 2, 9, 6, 4, 3, 8, 1, 5}

ここで、真ん中にある要素 4 を基準値に選択したとします。

ここでは基準値の選び方を、真ん中になる要素としていますが、一例としてそうしているだけです。実際には選び方にもポイントがあります。基準値の選び方で取り上げます。

4 を基準とした分割を行います。4 より小さい値をもった要素をデータ列の先頭付近に移動し、4 より大きい値をもった要素を末尾付近へ移動します。その結果は次のようになります。

{2, 3, 1, 4, 7, 9, 6, 8, 5}
          |
         基準値

次に、基準値より小さい側の集まりと、大きい側の集まりの中のそれぞれに、同じ操作を繰り返します。もし、集まりの中に要素が１個だけ、あるいは０個の場合は、その集まりについては何も行いません。

まず小さい側の集まりを見てみます。小さい側の集まりは {2, 3, 1} です。仮に、基準値を真ん中の 3 とすると、結果は次のようになります。() の中の要素は、今は相手にしていない部分を表します。

{2, 1, 3, (4, 7, 9, 6, 8, 5)}
       |
      基準値

このまま同じ操作を繰り返します。今度の基準値は 2 としましょう。

{1, 2, (3, 4, 7, 9, 6, 8, 5)}
    |
   基準値

基準値より小さい側の要素は１個、大きい側は０個になりました。これ以上は繰り返しても仕方がないので、これで終了します。

今度は、無視していた末尾側の集まりを相手にします。こちら側の集まりは {7, 9, 6, 8, 5} でした。基準値を、真ん中にある 6 とすると、次のような結果になります。

{(1, 2, 3, 4), 5, 6, 7, 9, 8}
                  |
                 基準値

小さい側の要素は１個になったので完了です。大きい側の集まり {7, 9, 8} は続行しましょう。今度の基準値は真ん中の 9 です。

{(1, 2, 3, 4, 5, 6), 7, 8, 9}
                           |
                          基準値

小さい側に要素が２つあるので続行します。すでに {7, 8} の順番になっているのでソート済みですが、そのこととは関係なく、要素の残りの個数だけで続行するべきかどうかを判断します。

今度の基準値は 7 です。

{(1, 2, 3, 4, 5, 6), 7, 8, (9)}
                     |
                    基準値

ここまでで、すべての要素は１つずつばらばらな状態まで細分化されたはずです。そして、この状態になると、すでに全体としてデータ列はソート済みになっています。


クイックソートのプログラム例 🔗

クイックソートの実装方法には、さまざまな形がありますが、ここではまず、先ほど説明した原理どおりに素直に実装してみます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void quick_sort(int* array, size_t size);
static void quick_sort_rec(int* array, int begin, int end);
static inline int select_pivot(const int* array, int begin, int end);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

    print_array( array, SIZE_OF_ARRAY(array) );
    quick_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
    // 配列全体を対象にする
    quick_sort_rec( array, 0, (int)(size - 1) );
}

/*
    クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array, int begin, int end)
{
    int pivot = select_pivot( array, begin, end );
    int i = begin;
    int j = end;

    while( 1 ){
        while( array[i] < pivot ){ ++i; }  // 基準値以上の値が見つかるまで右方向へ進めていく
        while( array[j] > pivot ){ --j; }  // 基準値以下の値が見つかるまで左方向へ進めていく

        if( i >= j ){ break; }  // 左右から進めてきたiとjがぶつかったらループを終える

        // 基準値の位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
        // 基準値の位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
        // 位置関係を交換する。
        SWAP( int, array[i], array[j] );

        // 次回に備えて、注目点をずらす
        i++;
        j--;
    }


    // 基準値の位置より左側に要素が２つ以上あれば、
    // その部分についてクイックソートを再帰させる
    if( i - begin >= 2 ){
        quick_sort_rec( array, begin, i - 1 );
    }

    // 基準値の位置より右側に要素が２つ以上あれば、
    // その部分についてクイックソートを再帰させる
    if( end - j >= 2 ){
        quick_sort_rec( array, j + 1, end );
    }
}

/*
    基準値を選ぶ
*/
inline int select_pivot(const int* array, int begin, int end)
{
    return array[(begin + end) / 2];  // 中央の要素を基準値とする
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果：

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

クイックソートの実装の中核となっているのは、quick_sort_rec関数ですが、main関数からは　quick_sort関数を呼び出すようにしています。quick_sort関数は、これまでの章で実装したソートアルゴリズムの関数と同じ引数・戻り値になっています。他のソートアルゴリズムを実装した関数と簡単に取り換えられるようにするために、このように実装しました。

quick_sort_rec関数を見ていきましょう。

quick_sort_rec関数には、ソート対象となる配列と、その範囲を指定しています。範囲を指定できるようにしているのは、要素を分割するたびに、処理の対象となる範囲が変わっていくことに対応するためです。

なお begin と end の型を int にしていますが、処理の過程で負数になることがあるので、符号無し整数型📘である size_t型で扱うと失敗します。

まず、基準値 pivot を決定します。基準値の決め方には工夫の余地があるので、select_pivot関数として分離しておきました。今回の実装は、ソート範囲の中央にある要素を基準値とする方法です。なお、関数呼び出しそのものによる処理時間の増加がもったいないので、（効果があるかどうかはコンパイラ次第ですが）インライン関数（Ｃ言語編第５７章）にしています。

while文の内側に入ると、すぐに２つの while文が現れます。この２つの while文は、基準値の位置よりも左側（添字が若い方）にあり、基準値よりも大きな値を持った要素の位置と、基準値の位置よりも右側にあり、基準値よりも小さな値を持った要素の位置を探しています。それぞれ、ソート範囲の両端から中央に向かって探します。

ここで発見された２つの要素は、基準値との大小関係が逆になっていますから、それぞれの位置を交換してやれば、正しい大小関係になります。

２つの while文の条件式📘は、現在の注目位置にある値と基準値が同じ値の場合には満たされません。このときにループを抜けます。そのため、基準値の位置を通り越して反対側にまで進んでしまうことはありません。これは、配列の範囲外アクセスのチェックが不要だということでもあります。

基準値が番兵（【探索】第２章）としての役割を果たしているといえます。

ソート範囲の両端から進めてきた２つの添字(i, j) がぶつかり合った時点で、外側の while文を抜け出します。これで、基準値による分割処理が完了します。

次は、基準位置の左側の集まりと、右側の集まりに対して同じ処理を繰り返します。この処理は、集まりに含まれている要素数が１個以下の場合には行いません。

対象範囲が変わるだけで、やりたい処理は同じなので、再帰呼び出し📘を使うと簡潔に書けます。quick_sort関数に直接処理を書かず、quick_sort_rec関数を作っているのはこのためです。

quick_sort_rec関数の再帰呼び出しは、それを取り囲む if文が条件を満たさなくなれば行われないので、再帰はいずれ終了します。再帰呼び出しが最後の段階まで終わったところで、クイックソート全体の処理も終了します。


再帰しないクイックソートの実装 🔗

再帰呼び出しを使ったクイックソートの実装は、コードが簡潔になる利点はあるものの、スタック領域📘が足りなくなる恐れがあります。ソート作業は、大量のデータに対して行うことも多いので、この問題は致命的です。

ここでいうスタックは、データ構造のスタック📘（【データ構造】第５章）ではなくメモリ内の領域のことです（結局のところ、データ構造のスタックの考え方でいいのですが）。関数呼び出しと、スタック領域の使われ方に関することは、Ｃ言語編第５３章で説明しています。

この問題は、自力でスタックを管理するようにして、再帰構造を取りやめれば解決できます。次のサンプルプログラムは、クイックソートを再帰しない方法で実装したものです。

スタックの実装には、コードライブラリにあるサンプル実装 ppps_int_stackを使用しています。性能的には、自力で無駄なく実装したほうがずっと速くなります。

#include <math.h>
#include <stdio.h>
#include "ppps_int_stack.h"

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void quick_sort(int* array, size_t size);
static void quick_sort_body(int* array, int begin, int end);
static inline int select_pivot(const int* array, int begin, int end);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

    print_array( array, SIZE_OF_ARRAY(array) );
    quick_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
    // 配列全体を対象にする
    quick_sort_body( array, 0, (int)(size - 1) );
}

/*
    クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
    // 必要なスタックサイズを計算する。
    // この実装では、log2 n 以上の容量があれば足りることが保証されているので、
    // これにしたがって決定する。
    // 
    // 最後の * 2 は、２つの値をセットで格納するため
    const size_t stack_size = (size_t)(log2((double)(end - begin + 1)) + 1) * 2;

    PPPSIntStack stack = ppps_int_stack_create(stack_size);

    ppps_int_stack_push( stack, (int)begin ); // 範囲の下限をスタックへ積む
    ppps_int_stack_push( stack, (int)end );   // 範囲の上限をスタックへ積む

    // スタックが空になるまで繰り返す
    while( !ppps_int_stack_is_empty(stack) ){

        // 範囲の情報をスタックから取り出す
        // スタックは後入れ先出しの構造なので、
        // 積んだときとは逆の順序で取り出さなければならない点に注意
        end = ppps_int_stack_pop( stack );
        begin = ppps_int_stack_pop( stack );

        while( 1 ){

            // 範囲が逆転していたら何もすることはない
            if( begin >= end ){
                break;
            }

            int pivot = select_pivot( array, begin, end );
            int i = begin;
            int j = end;

            while( 1 ){
                while( array[i] < pivot ){ ++i; }  // 基準値以上の値が見つかるまで右方向へ進めていく
                while( array[j] > pivot ){ --j; }  // 基準値以下の値が見つかるまで左方向へ進めていく

                if( i >= j ){ break; }  // 左右から進めてきたiとjがぶつかったらループを終える

                // 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
                // 基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
                // 位置関係を交換する。
                SWAP( int, array[i], array[j] );

                // 次回に備えて、注目点をずらす
                i++;
                j--;
            }

            // 左右の配列のうち、要素数が少ない方を先に処理する。
            // (i - begin) は左側の要素数、
            // (end - j) は右側の要素数を計算している。
            //
            // 後で処理する側の範囲情報をスタックへ積んでおく。
            if( i - begin < end - j ){
                // 右側の範囲情報をスタックへ積み、
                // 左側の範囲を先に処理する。
                ppps_int_stack_push( stack, j + 1 );
                ppps_int_stack_push( stack, end );
                end = i - 1;
            }
            else{
                // 左側の範囲情報をスタックへ積み、
                // 右側の範囲を先に処理する。
                ppps_int_stack_push( stack, begin );
                ppps_int_stack_push( stack, i - 1 );
                begin = j + 1;
            }
        }
    }

    ppps_int_stack_delete( stack );
}

/*
    基準値を選ぶ
*/
inline int select_pivot(const int* array, int begin, int end)
{
    return array[(begin + end) / 2];  // 中央の要素を基準値とする
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果：

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

ソート対象範囲が決まるたびに、スタックにその範囲情報（配列の上限と下限をあらわす添字のペア）を積みます。

スタックを２つ用意して、上限と下限を別個に管理しても構いません。

再帰呼び出しの代わりは、ループ構造です。スタックが空になるまで繰り返すようなループを構築し、すべてのソート処理はこの内側で行うようにします。

ループ内では、まずスタックから２つの値を取り出します。スタックには、ソート対象範囲を表す添字のペアが積まれているので、２つの値を取り出せば、それが今回のソート対象範囲です。

ソート対象範囲がわかれば、やることは再帰版と同じです。基準値を決めて、分割処理を行います。この部分の処理は特に変える必要はありません。

再帰版で、再帰呼び出しを行っていたところで、スタックへ範囲情報を積んでいます。


ところで、スタックの容量をどのくらい取ればいいのか、という問題があります。これが足りなかったら、結局、再帰版でスタック領域が足りなくなる問題と同じことが起こってしまいます。

基準値による分割を終えて、左右の要素の集まりの範囲をスタックへ積むとき、要素数が少ない側の部分配列を先に処理させるようにしています。言い換えると、要素数が大きい側をスタックに積んでいます。このように実装した場合、スタックの容量は、（データの総数を n個としたとき）log2 n 以上あれば足りることが保証されています。

この保証があることが、再帰版ではスタック領域が不足するかもしれないが、非再帰版ではスタックが足りることを保証できる理由です。

この保証を用いて、(log2(n) + 1) * 2; のようにしてスタック容量を決めることができます。+1 しているのは、log2関数が返した値よりも大きくなければならないからです。*2 しているのは、実際にスタックに積む情報を、配列の上限と下限の添字の “ペア” つまり 2個セットにしているからです。

ただ、このようにまじめに計算すると、（少なくともＣ言語では）コンパイル時📘に要素数を決定できない問題があります。結果、スタックを動的メモリ割り当て📘で確保せざるを得なくなり、余計な処理コストを払うことになります。要素数の最大が大体でもわかっているのであれば、手動で計算した結果を定数として使い、スタックの大きさをコンパイル時に確定させておいたほうが効率は良くなります。


クイックソートの性能 🔗

クイックソートの計算量は、平均的には O(n log n) です。これは前章のシェルソートの計算量 O(n1.25)～O(n1.5) よりもさらに良い性能です。実際に比較してみましょう。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_stack.h"

#define ARRAY_SIZE              1000000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void init_array(int* array, size_t size);
static void shell_sort(int* array, size_t size);
static void quick_sort(int* array, size_t size);
static void quick_sort_body(int* array, int begin, int end);
static inline int select_pivot(const int* array, int begin, int end);

int main(void)
{
    static int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    shell_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("shell_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    quick_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("quick_sort");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    シェルソート (昇順)
*/
void shell_sort(int* array, size_t size)
{
    // 最初の間隔 h を決める
    // 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
    // これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。
    size_t h = 1;
    for( size_t h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
        h = h_tmp;
    }

    while( h > 0 ){
        for( size_t i = h; i < size; ++i ){
            int tmp = array[i];

            if( array[i-h] > tmp ){  // 挿入が必要か先に調べる
                size_t j = i;

                do {
                    array[j] = array[j-h];
                    j -= h;
                } while( j >= h && array[j-h] > tmp );

                array[j] = tmp;
            }
        }
        h /= 3;  // 間隔を縮める
    }
}

/*
    クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
    // 配列全体を対象にする
    quick_sort_body( array, 0, (int)(size - 1) );
}

/*
    クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
    // 必要なスタックサイズを計算する。
    // この実装では、log2 n 以上の容量があれば足りることが保証されているので、
    // これにしたがって決定する。
    // 
    // 最後の * 2 は、２つの値をセットで格納するため
    const size_t stack_size = (size_t)(log2((double)(end - begin + 1)) + 1) * 2;

    PPPSIntStack stack = ppps_int_stack_create(stack_size);

    ppps_int_stack_push( stack, (int)begin ); // 範囲の下限をスタックへ積む
    ppps_int_stack_push( stack, (int)end );   // 範囲の上限をスタックへ積む

    // スタックが空になるまで繰り返す
    while( !ppps_int_stack_is_empty(stack) ){

        // 範囲の情報をスタックから取り出す
        // スタックは後入れ先出しの構造なので、
        // 積んだときとは逆の順序で取り出さなければならない点に注意
        end = ppps_int_stack_pop( stack );
        begin = ppps_int_stack_pop( stack );

        while( 1 ){

            // 範囲が逆転していたら何もすることはない
            if( begin >= end ){
                break;
            }

            int pivot = select_pivot( array, begin, end );
            int i = begin;
            int j = end;

            while( 1 ){
                while( array[i] < pivot ){ ++i; }  // 基準値以上の値が見つかるまで右方向へ進めていく
                while( array[j] > pivot ){ --j; }  // 基準値以下の値が見つかるまで左方向へ進めていく

                if( i >= j ){ break; }  // 左右から進めてきたiとjがぶつかったらループを終える

                // 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
                // 基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
                // 位置関係を交換する。
                SWAP( int, array[i], array[j] );

                // 次回に備えて、注目点をずらす
                i++;
                j--;
            }

            // 左右の配列のうち、要素数が少ない方を先に処理する。
            // (i - begin) は左側の要素数、
            // (end - j) は右側の要素数を計算している。
            //
            // 後で処理する側の範囲情報をスタックへ積んでおく。
            if( i - begin < end - j ){
                // 右側の範囲情報をスタックへ積み、
                // 左側の範囲を先に処理する。
                ppps_int_stack_push( stack, j + 1 );
                ppps_int_stack_push( stack, end );
                end = i - 1;
            }
            else{
                // 左側の範囲情報をスタックへ積み、
                // 右側の範囲を先に処理する。
                ppps_int_stack_push( stack, begin );
                ppps_int_stack_push( stack, i - 1 );
                begin = j + 1;
            }
        }
    }

    ppps_int_stack_delete( stack );
}

/*
    基準値を選ぶ
*/
inline int select_pivot(const int* array, int begin, int end)
{
    return array[(begin + end) / 2];  // 中央の要素を基準値とする
}

データ件数ごとの比較結果はこうなりました。

データ件数 シェルソート クイックソート
10000個 0.002秒 0.002秒
100000個 0.03秒 0.029秒
1000000個 0.335秒 0.263秒

データ件数が少ないとそれほど変わらないようですが、ppps_int_stack の実装には余分なものが含まれていることに原因があります。たとえば、スタック作成時に動的メモリ割り当て📘を行いますし、要素の push/pop も関数呼び出しなので、そのコストが加わっています。

どちらにしても、上記の結果は、筆者の環境での結果にすぎません。必ず、ご自身がターゲットにする環境で実測して判断を行ってください。

最悪の場合 🔗

前の項の実験では、クイックソートは確かに高速なようでした。

しかし、クイックソートの最悪時の計算量は O(n2)であり、これはバブルソート並みの性能です。つまり、高速にならない可能性があるということです。

クイックソートにとって最悪なときとは、基準値の位置で分割した結果、左側または右側にだけ要素がかたよってしまう場合です。

クイックソートの再帰処理（非再帰版ならループ処理）が終わる条件は、対象範囲の要素数が１個になったときです。ですから、できるだけ速く、対象範囲が絞り込まれていけば高速になりますし、なかなか絞り込めないと低速になります。

たとえば、データ件数が 1000個だったとします。

最高のケースは、初回の分割で 500個ずつに分割され、次の回でそれぞれが 250個、次は 125個・・・となっていく場合です。

最悪のケースは、初回の分割で 999個と 1個に分割され、999個の側を分割したら 998個と 1個になってしまう。次は 997個と 1個に・・・こんな状態が繰り返される場合です。

クイックソートが最高の性能を発揮するには、１回の分割ごとに、要素が基準値の位置の左右にちょうど半分ずつ振り分けられる必要があります。ちょうど半分半分とまではいわないにしても、それに近いぐらいに左右に振り分けられれば高速さを保てます。

意図的に、クイックソートの性能が最悪になるようなデータ列を作って実験してみます。先ほどのプログラムの中で、init_array関数を次のように書き換えます。

void init_array(int* array, size_t size)
{
    for( size_t i = 0; i < size / 2; ++i){
        array[i] = (int)i;
    }
    for( size_t i = size / 2; i < size; ++i){
        array[i] = (int)(size - i);
    }
}

このデータ列は、左半分は整列済み（昇順）、右半分は真逆（降順）に並んでしまっている状態です。このようなデータ列で、基準値を真ん中から選ぶと、すべての要素が基準値より小さい値をもっていることになるため、要素は左側に片寄ります。

このデータ列に対するソートを実測すると、次のようになりました。比較のため、ランダムなデータ列を使った場合の、同じ実装のクイックソートの結果も並べます。

データ件数 最悪時 ランダムなデータ列
10000個 0.055秒 0.002秒
100000個 4.715秒 0.029秒
1000000個 471.184秒 0.263秒

ここまで極端な差が出ます。

最悪時のときの 10万個の結果と、100万個の結果を比較すると、大体 100倍の時間になっており、たしかに O(n2) の計算量にまで落ち込んでいる様子がみえます（データ数が 10倍になったので、実行時間は 100倍に増えるであろう）。

このような最悪のケースは、基準値を選ぶ方法を工夫することである程度防げます。次の項で取り上げます。


基準値の選び方 🔗

「最悪の場合」のところで、データ列の並び方が悪いと、クイックソートの性能が悪化することを示しました。この問題への対策として、基準値の選び方を工夫する方法があります。

基準値の選び方としてよくあるのは、データ列から３つの要素を選び出し、そのメジアン（中央値）を基準値にする方法です。選び出す３つの要素はどれでもいいのですが、選び出すこと自体に余計な処理時間をかけては意味がないので、データ列の先頭、中央、末尾を使う方法がよく使われます。メジアンとは、いくつかの数値を昇順か降順に整列させたときに真ん中に来る値のことで、平均値とは異なります。

たとえば、(2, 6, 3, 7, 8) というデータ列があるとします。昇順に整列すると (2, 3, 6, 7, 8) なので、その真ん中にある 6 がメジアンです。

ちなみに、データ列が偶数個の場合は、真ん中と呼べる要素が２つありますが、その際には、その２つの要素の値の平均値を取ります。

３つの要素のメジアンを基準値として使う方法でクイックソートを実装し、最悪時の性能を調べてみます。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_stack.h"

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void init_array(int* array, size_t size);
static void quick_sort(int* array, size_t size);
static void quick_sort_body(int* array, int begin, int end);
static inline int select_pivot(const int* array, int begin, int end);
static int median3(int x, int y, int z);

int main(void)
{
    static int array[ARRAY_SIZE];

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    quick_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("quick_sort");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    for( size_t i = 0; i < size / 2; ++i ){
        array[i] = (int)i;
    }
    for( size_t i = size / 2; i < size; ++i ){
        array[i] = (int)(size - i);
    }
}

/*
    クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
    // 配列全体を対象にする
    quick_sort_body( array, 0, (int)(size - 1) );
}

/*
    クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
    // 必要なスタックサイズを計算する。
    // この実装では、log2 n 以上の容量があれば足りることが保証されているので、
    // これにしたがって決定する。
    // 
    // 最後の * 2 は、２つの値をセットで格納するため
    const size_t stack_size = (size_t)(log2((double)(end - begin + 1)) + 1) * 2;

    PPPSIntStack stack = ppps_int_stack_create(stack_size);

    ppps_int_stack_push( stack, (int)begin ); // 範囲の下限をスタックへ積む
    ppps_int_stack_push( stack, (int)end );   // 範囲の上限をスタックへ積む

    // スタックが空になるまで繰り返す
    while( !ppps_int_stack_is_empty(stack) ){

        // 範囲の情報をスタックから取り出す
        // スタックは後入れ先出しの構造なので、
        // 積んだときとは逆の順序で取り出さなければならない点に注意
        end = ppps_int_stack_pop( stack );
        begin = ppps_int_stack_pop( stack );

        while( 1 ){

            // 範囲が逆転していたら何もすることはない
            if( begin >= end ){
                break;
            }

            int pivot = select_pivot( array, begin, end );
            int i = begin;
            int j = end;

            while( 1 ){
                while( array[i] < pivot ){ ++i; }  // 基準値以上の値が見つかるまで右方向へ進めていく
                while( array[j] > pivot ){ --j; }  // 基準値以下の値が見つかるまで左方向へ進めていく

                if( i >= j ){ break; }  // 左右から進めてきたiとjがぶつかったらループを終える

                // 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
                // 基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
                // 位置関係を交換する。
                SWAP( int, array[i], array[j] );

                // 次回に備えて、注目点をずらす
                i++;
                j--;
            }

            // 左右の配列のうち、要素数が少ない方を先に処理する。
            // (i - begin) は左側の要素数、
            // (end - j) は右側の要素数を計算している。
            //
            // 後で処理する側の範囲情報をスタックへ積んでおく。
            if( i - begin < end - j ){
                // 右側の範囲情報をスタックへ積み、
                // 左側の範囲を先に処理する。
                ppps_int_stack_push( stack, j + 1 );
                ppps_int_stack_push( stack, end );
                end = i - 1;
            }
            else{
                // 左側の範囲情報をスタックへ積み、
                // 右側の範囲を先に処理する。
                ppps_int_stack_push( stack, begin );
                ppps_int_stack_push( stack, i - 1 );
                begin = j + 1;
            }
        }
    }

    ppps_int_stack_delete( stack );
}

/*
    基準値を選ぶ
*/
inline int select_pivot(const int* array, int begin, int end)
{
    return median3(array[begin], array[(begin + end) / 2], array[end-1]);
}

/*
    ３要素の中央値を求める
*/
int median3(int x, int y, int z)
{
    if( x < y ){
        if( y < z ){
            return y;
        }
        else if( z < x ){
            return x;
        }
        return z;
    }
    else{
        if( z < y ){
            return y;
        }
        else if( x < z ){
            return x;
        }
        return z;
    }
}

メジアンを求める一般的な方法は、ソートしてから中央の値を調べることですが（Ｃ言語編　逆引き「中央値を求める」）、３要素程度ならば、if文の連続でも十分です。

実行結果は次のようになりました。右の列は、基準値として中央にある要素の値を使う、これまでどおりの実装の場合の結果です（「最悪の場合」で計測したもの）。

データ件数 基準値は３要素のメジアン 基準値は中央にある要素
10000個 0.004秒 0.055秒
100000個 0.043秒 4.715秒
1000000個 0.371秒 471.184秒

大幅な改善がみられます。

念のため、データ列をランダムで生成したときの性能も確認すると、次のようになります。

データ件数 基準値は３要素のメジアン
10000個 0.003秒
100000個 0.042秒
1000000個 0.324秒

ほとんど変わりません。基準値の選び方として、３要素のメジアンを使う方法は、中央にある要素の値を使う方法よりも、適切だといえそうです。

最悪時の性能が大きく改善されたのは、分割の際に振り分けられる要素が片寄る可能性が減るからです。基準値を、たった１つの要素によって決めてしまうよりも、３つの要素に関与させたほうが、都合が悪い値を基準値に選んでしまう確率が減ります。

関与させる要素をさらに増やしたり、いっそ基準値を乱数で決めたりすれば、さらなる改善が図れる可能性はあります。ただ、基準値を決めることそのものに時間を取られるようになってしまうことや、ランダムに並んだデータ列には改善効果が薄い（そして大抵、データ列はランダムといって差し支えない並びをしているであろう）ことから、３要素程度で済ませておくほうが無難であるという考え方もあります。

この改善は、最悪時に対する軽減策であって、完璧な対策ではありません。３つの要素を関与させたとしても、そのメジアンがつねに都合の良い値になるという保証があるわけではないからです。メジアンが、中央にある要素の値とほとんど変わらない値になることもないとはいえません。

そのため、最悪時の性能が絶対に許容できない場合は、平均的には遅くなってしまいますが、性能があまり変動しないマージソート📘（第７章）やヒープソート📘（第８章）のようなアルゴリズムも検討するといいでしょう。

まとめ 🔗

クイックソートは、平均計算量が O(n log n)という、高い性能を誇るアルゴリズムです。しかし、最悪時の計算量は O(n2)です。

クイックソートは、安定なソート📘ではありません。

以下に列挙したように、性能をできるだけ最適化する方法がいくつかあります。

ただし、いずれの方法でも、最悪時に計算量が O(n2) に落ち込むことを完全に避けることはできません。もし、これを避けなければならないのであれば、そもそもクイックソート自体を諦めて、マージソート（第７章）やヒープソート（第８章）などの性能が安定的なアルゴリズムを採用した方が良いでしょう。


練習問題 🔗

問題①　基準値の選び方の１つに、ランダムでどれかの要素を使うという方法があります。この方法で実装して、パフォーマンスを測定してみてください。

問題②　再帰版と非再帰版とでは、パフォーマンスに差があるでしょうか。測定してください。

問題③　クイックソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら（n <10 程度が基準とされます）、その部分のソートに挿入ソート（第４章）を使うという方法があります。実装して、パフォーマンスを測定してください。


解答ページはこちら。

参考リンク 🔗


更新履歴 🔗

≪さらに古い更新履歴≫


前の章へ　（第５章　シェルソート（挿入ソートの改良））

次の章へ　（第７章　マージソート）

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る