アルゴリズムとデータ構造編【その他のアルゴリズム】 第4章 マージのアルゴリズム

先頭へ戻る

この章の概要

この章の概要です。


マージとは

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

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

配列をマージする

2つの配列をマージするにはどうすればいいでしょう。

確実に言えることは、2つの配列の要素数を合計した数以上の大きさの別の配列を用意する必要があるということです。マージ元の配列Aの要素数が 10 で、配列Bの要素数が 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" );
}

実行結果:

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

マージの処理をしているのは merge関数です。中身を見ると分かると思いますが、何てことはなく、配列a の要素を1つずつ配列result へ移し、続いて、配列b の要素を1つずつ配列result へ移すという操作をしているだけです。C言語なら、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 の要素数が分かっていなければできないことです。もし、要素数が分からない場合には、動的に領域を確保することになります。

さて、実用的に言えば、マージという操作はソート(【整列】第0章参照)を伴っていることが多いです。この場合、ソートされている配列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" );
}

実行結果:

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

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

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

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

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

まとめ

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

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

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


練習問題

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

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


解答ページはこちら


参考リンク



更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

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

'2013/1/6 新規作成。



前の章へ (第3章 簡易的な暗号化)

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

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー