マージのアルゴリズム | 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" );
}

実行結果：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

マージの処理をしているのは 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];


    // 配列 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" );
}

実行結果：

0 2 4 6 8 10 12 14 16 18
0 3 6 9 12
0 0 2 3 4 6 6 8 9 10 12 12 14 16 18

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

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

まとめ 🔗

２ウェイマージの手法を解説しました。

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

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


練習問題 🔗

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

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


解答ページはこちら。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

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

　新規作成。


前の章へ　（第３章　簡易的な暗号）

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

Programming Place Plus のトップページへ

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