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

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

問題①

問題① 元のデータ列が事前にソートされている範囲を変えると、実行時間はどのくらい増減しますか? ご自分の実行環境で確認してみてください。


本編の「性能」のところで使ったプログラムを改造して試してみます。

init_array関数に引数を追加して、ソート済みにする要素数も指定できるようにしました。

配列全体が未整列の場合、20%、40%、60%、80% が整列済みの場合、そして全体が整列済みの場合をそれぞれ調べてみます。

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

#define ARRAY_SIZE              50000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size, size_t sorted_size);
static void insertion_sort_ex(int* array, size_t size);

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


    init_array( array, ARRAY_SIZE, 0 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (0%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 2 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (20%)");
    
    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 4 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (40%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 6 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (60%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (80%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (100%)");

    return 0;
}

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

    size_t i;

    for( i = 0; i < sorted_size; ++i ){
        array[i] = (int)i;
    }

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

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

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

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

実行結果:

insertion_sort_ex (0%): 2.335000 seconds
insertion_sort_ex (20%): 1.748000 seconds
insertion_sort_ex (40%): 1.530000 seconds
insertion_sort_ex (60%): 1.391000 seconds
insertion_sort_ex (80%): 1.005000 seconds
insertion_sort_ex (100%): 0.000000 seconds

整列済みの部分が増えると、順当に高速になっていることが分かります。

問題②

問題② 改良版挿入ソートを、降順にソートするようにしてください。


不等号の向きを逆にするだけで実現できます。

大小比較を行っている箇所が2つあることに注意してください。書き換えたのは、if文の条件式と、do-while文の条件式の2か所です。

void insertion_sort_ex(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

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

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] < tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

問題③

問題③ 挿入位置を探すとき、二分探索(【探索】第4章参照)の考え方を使えば高速化を図れる可能性があります。改良版挿入ソートをこの方法で実装してください。


このような実装方法は、二分挿入ソートと呼ばれています。

前提として、二分探索を理解しなければなりません。【探索】第4章で説明していますが、わりと一般的な実装方法だと、同じ値が複数含まれているとき、どれを見つけ出すか不定になります。この問題によって、決定される挿入位置も不定(同じ値の集まりのどこが選ばれるかということなので、ソートできないわけではありません)になるため、不定にならない実装を使う必要があります。

/*
    二分挿入ソート (昇順)
*/
void binary_insertion_sort_ex(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){  // 挿入が必要か先に調べる

            // 挿入位置を二分探索で探す
            size_t lower = 0;
            size_t upper = i;
            while( lower < upper ){
                size_t mid = (lower + upper) / 2;

                if( array[mid] < tmp ){
                    lower = mid + 1;
                }
                else{
                    upper = mid;
                }
            }

            // 発見した挿入位置へ挿入
            size_t j;
            for( j = i; j > lower; --j ){
                array[j] = array[j-1];
            }
            array[j] = tmp;
        }
    }
}

元の改良版挿入ソートと、この二分挿入ソートの性能を比較してみましょう。

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

#define ARRAY_SIZE              50000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size, size_t sorted_size);
static void insertion_sort_ex(int* array, size_t size);
static void binary_insertion_sort_ex(int* array, size_t size);

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

    //
    // 事前ソートなし
    //

    init_array( array, ARRAY_SIZE, ARRAY_SIZE );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (0%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE );
    PPP_CHECK_PERFORM_BEGIN(1);
    binary_insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("binary_insertion_sort_ex (0%)");


    //
    // 事前に 80% までソート済み
    //

    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (80%)");

    init_array( array, ARRAY_SIZE, ARRAY_SIZE / 10 * 8 );
    PPP_CHECK_PERFORM_BEGIN(1);
    binary_insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("binary_insertion_sort_ex (80%)");

    return 0;
}

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

    size_t i;

    for( i = 0; i < sorted_size; ++i ){
        array[i] = (int)i;
    }

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

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

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

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

/*
    二分挿入ソート (昇順)
*/
void binary_insertion_sort_ex(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){  // 挿入が必要か先に調べる

            // 挿入位置を二分探索で探す
            size_t lower = 0;
            size_t upper = i;
            while( lower < upper ){
                size_t mid = (lower + upper) / 2;

                if( array[mid] < tmp ){
                    lower = mid + 1;
                }
                else{
                    upper = mid;
                }
            }

            // 発見した挿入位置へ挿入
            size_t j;
            for( j = i; j > lower; --j ){
                array[j] = array[j-1];
            }
            array[j] = tmp;
        }
    }
}

実行結果:

insertion_sort_ex (0%): 2.235000 seconds
binary_insertion_sort_ex (0%): 1.976000 seconds
insertion_sort_ex (80%): 2.179000 seconds
binary_insertion_sort_ex (80%): 1.941000 seconds

二分挿入ソートの方が良い結果を示しました。


参考リンク


更新履歴

’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

≪さらに古い更新履歴を展開する≫



第4章のメインページへ

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

Programming Place Plus のトップページへ



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