マージのアルゴリズム | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第４章

マージとは、「併合」とか「結合」という意味です。要するに、複数あるものを１つにまとめるということです。

広義には、複数のファイルを１つにまとめるだとか、複数あるデータベースを１つに統合することを含めますが、ここでは、複数のデータ列（配列（【データ構造】第１章）や連結リスト（【データ構造】第３章）など）を１つにまとめることを考えます。

配列をマージする

確実にいえることは、２つの配列の要素数を合計した数以上の大きさの別の配列を用意する必要があるということです。マージ元の配列Ａの要素数が 10 で、配列Ｂの要素数が 5 であれば、マージ結果の要素数は 15 になるのですから、要素数15 を許容できるだけの領域が必要です。

十分な大きさの配列を用意すれば、あとは割と単純です。配列Ａの内容をマージ後の配列へ移し、次に配列Ｂの内容をマージ後の配列へ移す。それだけのことです。

#include <stdio.h>

#define ARRAY_A_SIZE  (10)
#define ARRAY_B_SIZE  (5)
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void merge(int* result, const int* a, size_t asize, const int* b, size_t bsize);
static void print_array(const int* array, size_t size);

int main(void)
{
    int a[ARRAY_A_SIZE];
    int b[ARRAY_B_SIZE];
    int c[ARRAY_A_SIZE + ARRAY_B_SIZE];


    // 配列 a, b を初期化
    for( size_t i = 0; i < SIZE_OF_ARRAY(a); ++i ){
        a[i] = (int)i;
    }
    for( size_t i = 0; i < SIZE_OF_ARRAY(b); ++i ){
        b[i] = (int)(ARRAY_A_SIZE + i);
    }

    // マージ実行
    merge( c, a, SIZE_OF_ARRAY(a), b, SIZE_OF_ARRAY(b) );
    print_array( c, SIZE_OF_ARRAY(c) );

    return 0;
}

/*
    マージ
*/
void merge(int* result, const int* a, size_t asize, const int* b, size_t bsize)
{
    size_t i, j;

    i = 0;
    for( j = 0; j < asize; ++j ){
        result[i] = a[j];
        ++i;
    }
    for( j = 0; j < bsize; ++j ){
        result[i] = b[j];
        ++i;
    }
}

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

マージの処理をしているのは merge関数です。配列a の要素を１つずつ配列result へ移し、続いて、配列b の要素を１つずつ配列result へ移すという操作をしているだけです。

/*
    マージ
*/
void merge(int* result, const int* a, size_t asize, const int* b, size_t bsize)
{
    memmove( result, a, sizeof(int) * asize );
    memmove( &result[asize], b, sizeof(int) * bsize );
}

このサンプルプログラムでは、マージ結果を格納する配列を静的に用意していますが、これは事前に（コンパイル段階で）配列a, b の要素数が分かっていなければできないことです。もし、要素数が分からない場合には、動的に領域を確保することになります。

２ウェイマージ

実用的には、マージという操作はソート（【整列】第０章参照）を伴っていることが多いです。この場合、ソートされている配列a, b の要素を、やはりソート済みな配列 c になるようにマージするということです。

仮に昇順にソートするとしましょう。この場合、配列a, b の先頭の要素同士を比較して、小さい方の要素を取り出して配列 c へ格納します。これを繰り返していって、配列a, b のいずれかが空になったら、残っている方の配列の要素はそのまま配列 c へ格納します。

このように、２つのデータ列をマージして、ソートされたマージ結果を得る方法を、２ウェイマージと呼びます。この手法は配列に限らず、連結リストのようなデータ構造でも、ファイルの結合にでも応用できます。

#include <stdio.h>

#define ARRAY_A_SIZE  (10)
#define ARRAY_B_SIZE  (5)
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void merge(int* result, const int* a, size_t asize, const int* b, size_t bsize);
static void print_array(const int* array, size_t size);

int main(void)
{
    int a[ARRAY_A_SIZE];
    int b[ARRAY_B_SIZE];
    int c[ARRAY_A_SIZE + ARRAY_B_SIZE];


    // 配列 a, b を初期化
    for( size_t i = 0; i < SIZE_OF_ARRAY(a); ++i ){
        a[i] = (int)(i * 2);
    }
    for( size_t i = 0; i < SIZE_OF_ARRAY(b); ++i ){
        b[i] = (int)(i * 3);
    }

    // マージ実行
    merge( c, a, SIZE_OF_ARRAY(a), b, SIZE_OF_ARRAY(b) );

    print_array( a, SIZE_OF_ARRAY(a) );
    print_array( b, SIZE_OF_ARRAY(b) );
    print_array( c, SIZE_OF_ARRAY(c) );

    return 0;
}

/*
    マージ
*/
void merge(int* result, const int* a, size_t asize, const int* b, size_t bsize)
{
    size_t i = 0;
    size_t j = 0;
    size_t k = 0;

    while( k < asize + bsize ){
        if( i >= asize ){
            // 配列 a の終端に行き着いていたら、残された配列 b の要素を全コピー
            while( j < bsize ){
                result[k++] = b[j++];
            }
        }
        else if( j >= bsize ){
            // 配列 b の終端に行き着いていたら、残された配列 a の要素を全コピー
            while( i < asize ){
                result[k++] = a[i++];
            }
        }
        else{
            // 配列 a と b の先頭要素で、小さい方を result へ
            if( a[i] <= b[j] ){
                result[k++] = a[i++];
            }
            else{
                result[k++] = b[j++];
            }
        }
    }
}

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

先ほどの説明どおり、先頭の要素同士を比較して、小さい方を配列 result へ移しています。もし、一方の配列がすでに末尾まで行き着いていたら、他方の配列の要素を一気に resule へ移します。

このようにマージを実装するとソートの役割を果たせます。これはマージソート（【整列】第７章）というソートアルゴリズムの原理と同じです。

まとめ

この手法は、先頭の要素にさえアクセスできれば、それぞれのデータ列を１つにまとめた上で、ソート済みな状態を作り出せます。テープ型の記憶媒体のように、先頭からの順次アクセスしか行えない場面において、このアルゴリズムは真価を発揮します。

配列をマージする際には、マージ元の配列の要素数の合計と同じだけの作業用領域が必要になることが欠点です。マージ元の配列が非常に巨大であると、メモリ不足に陥る可能性があります。

練習問題

問題①　２つの単方向線形リスト（【データ構造】第３章）をマージするプログラムを作成してください。

問題②　１行ごとに１つの文字列（10文字以内）が記述された２つのテキストファイルを、文字列の昇順に並ぶようにマージして、１つのテキストファイルを作り出すプログラムを作成してください。

参考リンク

更新履歴

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

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

この章の概要

マージとは

配列をマージする

２ウェイマージ

まとめ

練習問題

参考リンク

更新履歴