マージのアルゴリズム | 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];
    int i;


    /* 配列 a, b を初期化 */
    for( i = 0; i < SIZE_OF_ARRAY(a); ++i ){
        a[i] = i;
    }
    for( i = 0; i < SIZE_OF_ARRAY(b); ++i ){
        b[i] = 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)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

マージの処理をしているのは merge関数です。中身を見ると分かると思いますが、何てことはなく、配列a の要素を１つずつ配列result へ移し、続いて、配列b の要素を１つずつ配列result へ移すという操作をしているだけです。Ｃ言語なら、memmove関数を使えば、もっと短く書けます。

/*
    マージ
*/
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];
    int i;


    /* 配列 a, b を初期化 */
    for( i = 0; i < SIZE_OF_ARRAY(a); ++i ){
        a[i] = i * 2;
    }
    for( i = 0; i < SIZE_OF_ARRAY(b); ++i ){
        b[i] = 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, j, k;

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

    for( i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

merge関数の中を書き換えています。していることは先ほどの説明通りで、先頭要素同士を比較して、小さい方を配列 result へ移すことです。もし、一方の配列が既に末尾まで行き着いていたら、他方の配列の要素を一気に resule へ移しています。

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

マージのアルゴリズムとしては、最初から２つのデータ列があるところから話が始まりますが、マージソートでは、１つのデータ列をソートすることが主目的なので、複数のデータ列へ分割するところから話が始まります。分割できれば、それを上記のようなソートを兼ねたマージ処理によってソートできます。

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

まとめ

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

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

練習問題

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

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

参考リンク

更新履歴

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

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

この章の概要

マージとは

配列をマージする

まとめ

練習問題

参考リンク

更新履歴