マージのアルゴリズム | 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文字以内）が記述された２つのテキストファイルを、文字列の昇順に並ぶようにマージして、１つのテキストファイルを作り出すプログラムを作成してください。

解答ページはこちら。

参考リンク 🔗

Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
Programming Place Plus　アルゴリズムとデータ構造編　リンク集
　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

2019/12/27
- 全体的に見直して、大幅に修正
2019/9/4
- 対応規格を C95 から C99 へ上げる
  - コメントに // を使う
2019/9/2
- 対応規格を C95 から C99 へ上げる
  - ループ制御変数を for文の初期設定式で宣言するように修正
’2015/12/27
- SIZE_OF_ARRAYマクロの定義を修正。
’2015/2/21
- サンプルプログラムで、ファイルスコープでよい関数に static を付加。
’2013/1/6
- 新規作成。

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

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

Programming Place Plus のトップページへ

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