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

問題①

問題①　ボトムアップ方式のマージソートで、連結リストをソートするプログラムを作成してください（これはそれほど簡単にはいきません。あるデータ構造を併用することがポイントです）

あるデータ構造とはキュー（【データ構造】第６章参照）です。ここでは、コードライブラリの ppps_int_queue を、連結リストを格納できるように型を修正して使っています。

#include <stdio.h>
#include "ppps_int_slist.h"
#include "queue.h"

static void merge_sort(PPPSIntSlist list);
static PPPSIntSlist merge_sort_bottomup(PPPSIntSlist list);
static PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b);

int main(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, 2 );
    ppps_int_slist_add_tail( list, 9 );
    ppps_int_slist_add_tail( list, 6 );
    ppps_int_slist_add_tail( list, 4 );
    ppps_int_slist_add_tail( list, 3 );
    ppps_int_slist_add_tail( list, 8 );
    ppps_int_slist_add_tail( list, 5 );
    ppps_int_slist_add_tail( list, 1 );


    puts( "ソート前" );
    ppps_int_slist_print( list );

    merge_sort( list );

    puts( "ソート後" );
    ppps_int_slist_print( list );


    ppps_int_slist_delete( list );

    return 0;
}

/*
    マージソート (昇順)
*/
void merge_sort(PPPSIntSlist list)
{
    if( list == NULL ){
        return;
    }

    // リスト全体を対象にする
    PPPSIntSlist result = merge_sort_bottomup( list );

    list->next = result;
}

/*
    マージソート (昇順)
*/
PPPSIntSlist merge_sort_bottomup(PPPSIntSlist list)
{
    PPPSIntSlist result = NULL;

    if( list == NULL || list->next == NULL ){
        return result;
    }

    int size = ppps_int_slist_count( list );
    Queue queue = queue_create( size );

    // リストの要素をキューへ登録
    PPPSIntSlist p = list->next;
    while( p != NULL ){
        PPPSIntSlist q = p->next;  // next は NULL にするので先に保存しておく
        p->next = NULL;  // 独立した要素として登録するため next は NULL に
        queue_enqueue( queue, p );  // キューへ登録
        p = q;  // 保存しておいた next に復帰
    }

    // 初回の enqueue に備えて、１要素だけ取り出しておく
    queue_try_dequeue( queue, &result );

    while( !queue_is_empty(queue) ){
        PPPSIntSlist a, b;

        // マージ結果をキューへ戻す
        // 初回だけは、while文に入る前に dequeue しておいた要素が戻される
        queue_enqueue( queue, result );

        // キューから、マージ対象の２つの要素を取り出す
        // これらの要素は、初回は要素数１のリストだが、２回目以降は前回までのマージ結果である
        if( !queue_try_dequeue( queue, &a ) ){
            a = NULL;
        }
        if( !queue_try_dequeue( queue, &b ) ){
            b = NULL;
        }

        // 取り出された要素同士をマージ
        result = merge( a, b );
    }

    queue_delete( queue );

    return result;
}

/*
    マージ
*/
PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b)
{
    struct PPPSIntSlist_tag result;
    PPPSIntSlist x = &result;

    // リストをマージ
    while( a != NULL && b != NULL ){

        // 昇順にソートするので、小さい方の要素を優先する。
        // == の場合に、前半の側を優先すると安定なソートになる
        if( a->value <= b->value ){
            x->next = a;
            x = x->next;
            a = a->next;
        }
        else{
            x->next = b;
            x = x->next;
            b = b->next;
        }
    }

    // 残っている要素を、末尾へ連結
    if( a == NULL ){
        x->next = b;
    }
    else{
        x->next = a;
    }

    return result.next;
}

// queue.h

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

#include <stdbool.h>
#include "ppps_int_slist.h"


/*
    キュー型
*/
typedef struct Queue_tag* Queue;


/*
    キューを作る

    引数：
        size:   格納できる要素数
    戻り値：
        作成されたキュー。
        使い終わったら、queue_delete関数に渡して削除する。
*/
Queue queue_create(size_t size);

/*
    キューを削除する

    引数：
        queue:  キュー
*/
void queue_delete(Queue queue);

/*
    キューに要素を入れる

    引数：
        queue:  キュー
        value:  入れる要素
*/
void queue_enqueue(Queue queue, PPPSIntSlist value);

/*
    キューから要素を取り出す

    引数：
        queue:  キュー
    戻り値：
        取り出された要素

    要素が空の場合の動作は未定義。
*/
PPPSIntSlist queue_dequeue(Queue queue);

/*
    キューから要素を取り出す (成否判定付き)

    引数：
        queue:  キュー
        p:      取り出された要素を受け取るアドレス。
    戻り値：
        要素を取り出せたら true、取り出せなかったら false を返す。
        false が返された場合は、引数p が指す先には何も格納されない。
*/
bool queue_try_dequeue(Queue queue, PPPSIntSlist* p);

/*
    キューが空かどうか調べる

    引数：
        queue:  キュー
    戻り値：
        キューが空であれば true を返し、空でなければ false を返す。
*/
bool queue_is_empty(Queue queue);


#endif

// queue.h

#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static size_t get_next_index(Queue queue, size_t index);
static void* xmalloc(size_t size);


struct Queue_tag {
    PPPSIntSlist*    data;    // 要素を格納する動的配列
    size_t           size;    // data の要素数
    size_t           front;   // 先頭の要素の位置
    size_t           tail;    // 末尾の要素の位置
};


/* キューを作る */
Queue queue_create(size_t size)
{
    // front == tail を空の状態にしようとすると、配列全体を使い切った状態を作れない。
    // そこで、指定された size を +1 して、１つ余分に領域を確保しておく。
    size += 1;

    struct Queue_tag* queue = xmalloc( sizeof(struct Queue_tag) );
    queue->data  = xmalloc( sizeof(PPPSIntSlist) * size );
    queue->size  = size;
    queue->front = 0;
    queue->tail  = 0;

    return queue;
}

/* キューを削除する */
void queue_delete(Queue queue)
{
    free( queue->data );
    free( queue );
}

/* キューに要素を入れる */
void queue_enqueue(Queue queue, PPPSIntSlist value)
{
    assert( get_next_index(queue, queue->tail) != queue->front );

    queue->data[queue->tail] = value;

    // 次に要素を入れるときに使う位置を求める
    // リングバッファ構造なので、単純に +1 するだけではダメ
    queue->tail = get_next_index( queue, queue->tail );
}

/* キューから要素を取り出す */
PPPSIntSlist queue_dequeue(Queue queue)
{
    assert( !queue_is_empty(queue) );

    PPPSIntSlist pop_value = queue->data[queue->front];

    // 先頭から要素が１つ取り出されるので、先頭位置を更新する
    // リングバッファ構造なので、単純に +1 するだけではダメ
    queue->front = get_next_index( queue, queue->front );

    return pop_value;
}

/* キューから要素を取り出す (成否判定付き) */
bool queue_try_dequeue(Queue queue, PPPSIntSlist* p)
{
    assert( p != NULL );

    if( queue_is_empty(queue) ){
        return false;
    }

    *p = queue->data[queue->front];

    // 先頭から要素が１つ取り出されるので、先頭位置を更新する
    // リングバッファ構造なので、単純に +1 するだけではダメ
    queue->front = get_next_index( queue, queue->front );

    return true;
}

/* キューが空かどうか調べる */
bool queue_is_empty(Queue queue)
{
    return queue->front == queue->tail;
}


/* １つ後ろの添字を取得する */
size_t get_next_index(Queue queue, size_t index)
{
    return (index + 1) % queue->size;
}

/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

実行結果：

まず、キューを ppps_int_slist_count関数を使って作成します。

連結リスト内の要素数を数えて、その要素数を渡していますが、実際に連結リスト内の要素をたどって要素数を数えると、（要素数によっては）大幅に速度低下を招くので、実用上は注意しなければなりません。

キューを作成したら、連結リストの各要素を１要素ずつの細切れ状態にしてキューへ格納します。これは、ボトムアップ方式なので、「ソート前のデータ列の要素を、それぞれ長さ１の列とみなす」ためです。

マージ過程では、キューから要素を２つ取り出してマージし、その結果を再びキューへ戻すことを繰り返せば、ソートを実現できます。merge関数は、本編の実装のままです。

問題②

問題②　マージソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら、その部分のソートに挿入ソート（第４章）を使うという方法があります。この方法で、トップダウン方式の配列に対するマージソートを改造して、パフォーマンスを測定してください（前章の練習問題③では、クイックソートに対して、同じ方法による性能改善を取り上げています）。

変更されたマージソートでパフォーマンスを計測するプログラムは、次のようになります。

#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 merge_sort(int* array, size_t size);
static void merge_sort_rec(int* array, size_t begin, size_t end, int* work);
static void insertion_sort_ex(int* array, int begin, int end);
static void print_array(const int* array, size_t size);

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

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    merge_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("merge_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 merge_sort(int* array, size_t size)
{
    // 作業用領域を確保
    int* work = malloc( sizeof(int) * size );

    // 配列全体を対象にする
    merge_sort_rec( array, 0, size - 1, work );

    free( work );
}

/*
    マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, size_t begin, size_t end, int* work)
{
    static const int SMALL_SIZE = 10;  // 挿入ソートに切り替える要素数

    // 要素が１つしかなければ終了
    if( begin >= end ){
        return;
    }

    if( end - begin >= SMALL_SIZE ){
        // ２つのデータ列に分割して、それぞれを再帰的に処理
        size_t mid = (begin + end) / 2;
        merge_sort_rec( array, begin, mid, work );
        merge_sort_rec( array, mid + 1, end, work );

        // マージ
        {
            // 前半の要素を作業用配列へ
            for( size_t i = begin; i <= mid; ++i){
                work[i] = array[i];
            }

            // 後半の要素を逆順に作業用配列へ
            for( size_t i = mid + 1, j = end; i <= end; ++i, --j){
                work[i] = array[j];
            }

            // 作業用配列の両端から取り出した要素をマージ
            {
                size_t i = begin;
                size_t j = end;
                for( size_t k = begin; k <= end; ++k) {

                    // 昇順にソートするので、小さい方の要素を結果の配列へ移す。
                    // == の場合に、前半の側を優先すると安定なソートになる
                    if( work[i] <= work[j] ){
                        array[k] = work[i];
                        ++i;
                    }
                    else{
                        array[k] = work[j];
                        --j;
                    }
                }
            }
        }
    }
    else{
        // データ範囲が狭ければ、挿入ソートに切り替える
        insertion_sort_ex( array, begin, end );
    }
}

/*
    改良版挿入ソート (昇順)
*/
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;
        }
    }
}

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

変更前のマージソートと、変更後のマージソートとで、同じデータを使ってパフォーマンスを計測すると、次のような結果になりました。

データ件数変更前	変更後
10000個 0	.002秒 0.	002秒
100000個 0	.026秒 0.	020秒
1000000個 0	.266秒 0.	215秒
10000000個 2	.956秒 2.	321秒

効果が出ているようです。

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

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

問題①

問題②

参考リンク

更新履歴