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

トップページ – アルゴリズムとデータ構造編 – 【整列アルゴリズム】第６章

問題① 🔗

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


以下の３つの方法を比較したいと思います。

  1. 対象範囲の中央にある要素を基準値とする
  2. 先頭、中央、末尾の３要素のメジアンを基準値とする
  3. ランダムで選び出した要素を基準値とする

大量のデータを使うので、スタックサイズの問題を避けるために、非再帰版の実装を用います。

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

// 基準値の選び方
// 1: 中央の要素を基準値とする
// 2: ３要素のメジアンを基準値とする
// 3: ランダムな要素を基準値とする
#define SELECT_PIVOT_TYPE  (3)

#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; }
#define MEDIAN3(x,y,z)       \
    (x < y)              \
      ? (y < z)          \
          ? (y)          \
          : (z < x)      \
              ? (x)      \
              : (z)      \
      : (z < y)          \
          ? (y)          \
          : (x < z)      \
              ? (x)      \
              : (z)


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);

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)
{
    srand(0);

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

/*
    クイックソート (昇順)
*/
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)
{
#if SELECT_PIVOT_TYPE == 1
    return array[(begin + end) / 2];  // 中央の要素を基準値とする

#elif SELECT_PIVOT_TYPE == 2
    return MEDIAN3(array[begin], array[(begin + end) / 2], array[end-1]);  // ３要素のメジアンを基準値とする
    
#elif SELECT_PIVOT_TYPE == 3
    return array[rand() % (end - begin) + begin];  // ランダムな要素を基準値とする
    
#else
    #error "invalid SELECT_PIVOT_TYPE value"
#endif
}

SELECT_PIVOT_TYPEマクロの置換後の値を、1、2、3 のいずれかに変更して、実行します。メジアンを使う方法に関しては、関数呼び出しのコストが入らないように、マクロによる実装に置き換えてあります。

これらで、パフォーマンスを比較した結果は、以下のようになりました。

データ件数 方法１ 方法２ 方法３
10000個 0.001秒 0.001秒 0.001秒
100000個 0.003秒 0.003秒 0.003秒
1000000個 0.032秒 0.041秒 0.032秒

ほとんど差は見られません。

次に、最悪のケースのデータで試します。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.1秒 0.0秒 (測定不能) 0.0秒 (測定不能)
100000個 8.053秒 0.006秒 0.002秒
1000000個 822.593秒 (13.7分) 0.077秒 0.029秒

方法１は、計算量がほぼ O(n2) になってしまっていることが見て取れます。データ件数が 10倍になると、処理時間がほぼ 102倍に増加しています。方法２と方法３では、いずれもこの傾向は見られず、ほぼ O(n log n) の高い性能が発揮できているようです。

方法２よりも方法３の方がやや高速なようですが、これは単に計算式が簡単になるからでしょう。方法２では、メジアンを求める際に if文を数回実行しなければなりませんから、ここで負荷が生じています。

問題② 🔗

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


データ内容はランダムで選び出したものを、基準値の選出には３要素のメジアンによる方法を使ったもので測定します。

非再帰版は、本編での解説どおりのプログラムでは ppps_int_stack を使っているため、push や pop のたびに関数呼び出しが起こるなど、速度を落としています。

そこで、スタックの実装をすべて展開して、次のようなコードで試しました。また、スタックとして使う配列の要素数を定数で指定するため、スタックサイズの計算を変えています。

void quick_sort_body(int* array, int begin, int end)
{
    int stack[64];
    int sp = 0;

    stack[sp++] = begin;
    stack[sp++] = end;

    // スタックが空になるまで繰り返す
    while( sp > 0 ){

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

        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 ){
                // 右側の範囲情報をスタックへ積み、
                // 左側の範囲を先に処理する。
                stack[sp++] = j + 1;
                stack[sp++] = end;
                end = i - 1;
            }
            else{
                // 左側の範囲情報をスタックへ積み、
                // 右側の範囲を先に処理する。
                stack[sp++] = begin;
                stack[sp++] = i - 1;
                begin = j + 1;
            }
        }
    }
}

すると、次の結果が得られました。

データ件数 再帰版 非再帰版
10000個 0.002秒 0.002秒
100000個 0.021秒 0.019秒
1000000個 0.192秒 0.171秒
10000000個 1.944秒 1.773秒

若干ですが、非再帰版の方が速くなりました。一般的に、再帰版よりも非再帰版の方が高速になります。

問題③ 🔗

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


本編でつかった非再帰版を改造します。

#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);
static void insertion_sort_ex(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);
    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)
{
    static const int SMALL_SIZE = 10;  // 挿入ソートに切り替える要素数

    // 必要なスタックサイズを計算する。
    // この実装では、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;
            }

            // 対象の要素数が少なければ、挿入ソートに切り替える
            if( end - begin >= SMALL_SIZE ){
                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;
                }
            }
            else {
                insertion_sort_ex( array, begin, end );
                break;
            }
        }
    }

    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;
    }
}

/*
    改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, int begin, int end)
{
    for( int i = begin + 1; i <= end; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){ 
            int j = i;

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

            array[j] = tmp;
        }
    }
}

結果は次のようになりました。

データ件数 通常版 挿入ソートへの切り替え付き
10000個 0.003秒 0.001秒
100000個 0.042秒 0.022秒
1000000個 0.324秒 0.214秒

結果を見ると、挿入ソートへの切り替えを行うようにした方が高速になっています。確かに効果があるようです。

この手法は、対象の要素数があまりにも少ないと、クイックソートの分割処理が非効率になってくるため、ある程度のところで分割をやめてしまった方が良いということに由来しています。挿入ソートを選ぶ理由は、ある程度でも整列済みになっていると、より高速になるという挿入ソートならではの特徴が生かせるからです。


なお、次のようにスタックの実装も展開してみると、

/*
    クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
    static const int SMALL_SIZE = 10;  // 挿入ソートに切り替える要素数

    int stack[64];
    int sp = 0;

    stack[sp++] = begin;
    stack[sp++] = end;

    // スタックが空になるまで繰り返す
    while( sp > 0 ){

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

        while( 1 ){

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

            // 対象の要素数が少なければ、挿入ソートに切り替える
            if( end - begin >= SMALL_SIZE ){
                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 ){
                    // 右側の範囲情報をスタックへ積み、
                    // 左側の範囲を先に処理する。
                    stack[sp++] = j + 1;
                    stack[sp++] = end;
                    end = i - 1;
                }
                else{
                    // 左側の範囲情報をスタックへ積み、
                    // 右側の範囲を先に処理する。
                    stack[sp++] = begin;
                    stack[sp++] = i - 1;
                    begin = j + 1;
                }
            }
            else {
                insertion_sort_ex( array, begin, end );
                break;
            }
        }
    }
}

次のような結果が得られました。

データ件数 スタックの実装を展開 スタック展開前
10000個 0.001秒 0.001秒
100000個 0.016秒 0.022秒
1000000個 0.19秒 0.214秒


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

≪さらに古い更新履歴≫

　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

　問題②の解答例がコンパイルエラーになっていたのを修正。

　新規作成。


第６章のメインページへ

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

Programming Place Plus のトップページへ

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