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

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

問題① 🔗

問題①　間隔 h を、1,2,4,8,16,32… のような数列から選んだ場合の性能を調べてください。


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

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

static void init_array(int* array, size_t size);
static void shell_sort(int* array, size_t size);
static void shell_sort2(int* array, size_t size);

int main(void)
{
    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);
    shell_sort2( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("shell_sort2");

    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 ){
            size_t j;

            int tmp = array[i];
            for( j = i; j >= h && array[j-h] > tmp; j -= h ){
                array[j] = array[j-h];
            }
            array[j] = tmp;
        }
        h /= 3;  // 間隔を縮める
    }
}

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

    while( h > 0 ){
        for( size_t i = h; i < size; ++i ){
            size_t j;

            int tmp = array[i];
            for( j = i; j >= h && array[j-h] > tmp; j -= h ){
                array[j] = array[j-h];
            }
            array[j] = tmp;
        }
        h /= 2;  // 間隔を縮める
    }
}

実行結果：

shell_sort: 0.027000 seconds
shell_sort2: 0.083000 seconds

shell_sort関数は、本編での実装と同じです。

shell_sort2関数は、数列を 1,2,4,8,16,32,… という数列を使っています。こちらの方が低速になりました。

間隔 h の決め方によって、計算量自体に変化が出てきます。データ件数を変えて検証してみましょう。

データ件数 shell_sort関数 shell_sort2関数
1000個 0秒 (計測不能) 0秒 (計測不能)
10000個 0.002秒 0.005秒
100000個 0.027秒 0.106秒
1000000個 0.335秒 2.587秒

シェルソートの計算量は、O(n1.25)～O(n1.5) 程度です。データ件数が 10倍 になったとき、O(n1.25) に近い実装では、処理時間は 17.8倍程度の増加。O(n1.5) であれば 31.6倍程度の増加となるはずです。

実測値によると、shell_sort関数の処理時間は 14倍程度増加しています。一方、shell_sort2関数の方は 25倍程度増加しています。そのため、shell_sort関数は良い方の計算量に近く、shell_sort2関数は悪い方の計算量に近いことが分かります。

問題② 🔗

問題②　改良版挿入ソートとシェルソートにおいて、要素の位置を交換する回数がどの程度異なるか調べてください


たとえば、1万個のランダムなデータ列で調べてみます。

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

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

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

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

    
    init_array( array, SIZE_OF_ARRAY(array) );
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    
    init_array( array, SIZE_OF_ARRAY(array) );
    shell_sort( array, SIZE_OF_ARRAY(array) );

    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 insertion_sort_ex(int* array, size_t size)
{
    int count = 0;

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

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

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

            array[j] = tmp;
        }
    }

    printf("%d\n", count);
}

/*
    シェルソート (昇順)
*/
void shell_sort(int* array, size_t size)
{
    int count = 0;

    // 最初の間隔 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];
                    ++count;
                    j -= h;
                } while( j >= h && array[j-h] > tmp );

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

    printf("%d\n", count);
}

実行結果：

24968371
175499

それぞれの関数に変数count を追加し、要素を交換しているコード array[j] = array[j-1]; や array[j] = array[j-h]; が実行される回数を数えています。

結果、挿入ソートの方が圧倒的に多くの回数の交換が起きていることが分かりました。シェルソートでは、大まかなソートが何度も行われることによって、ゆるくソートされた状態になるため、if( array[i-h] > tmp ) のところで、挿入不要（よって交換も起きない）と判断される機会が多くなるためです。

この差が、両者の速度の差になります。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

≪さらに古い更新履歴≫

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

　コードライブラリのパス変更に伴い、リンクを修正。

　新規作成。


第５章のメインページへ

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

Programming Place Plus のトップページへ

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