マージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

マージソート解説ページのアイキャッチ

このページでは「マージソート」について解説し、さらにC言語でマージソートを実装したプログラムと、そのプログラムの解説をしていきたいと思います。

マージソートとは

マージソートとはソートのアルゴリズムの1つです。

下のページで「クイックソート」について解説しましたが、

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

このクイックソートに比べると、このページで紹介するマージソートには下記のような特徴があります

  • クイックソートに比べて処理速度が安定している
  • クイックソートに比べて使用メモリ量が多い

マージソートの考え方

マージソートは、与えられたデータの集合を下記の考え方によってソートするアルゴリズムになります。

  • 集合を中央で2つに分割する
  • 分割後の各集合のデータをそれぞれソートする
  • ソート済みの各集合をマージする
    1. 各集合のまだマージされていないデータの中から先頭のデータを抽出する
    2. 抽出したデータの中から一番小さいものをマージする
    3. 全データがマージされていなければ 1. に戻る
MEMO

上記は昇順にソートする場合の考え方になります

降順にソートする場合は「小さい」を「大きい」に読み替えてください

スポンサーリンク

集合のマージ

マージソートの1番のポイントは「ソート済みの各集合をマージする」ところです。

マージとは「結合する」「合体する」「併合する」などの意味を持つ言葉になります。

下記の2つのソート済みの各集合をマージする様子を図を使って確認してみましょう。

マージを行う2つの集合

まず2つの集合の先頭のデータを比較し、小さい方をマージ先の集合にマージします。

2つの先頭のデータの小さい方をマージする様子1

続いて、2つの集合それぞれにおいて、まだマージされていないデータの中から先頭のものを抽出して比較し、小さい方をマージ先の集合にマージします。マージ済みのデータは灰色で表しています。

2つの先頭のデータの小さい方をマージする様子2

同じ感じでどんどんマージを行っていきます。次は下の図のようになり、

2つの先頭のデータの小さい方をマージする様子3

その次は下の図のようにマージされていきます。

2つの先頭のデータの小さい方をマージする様子4

最後は下の図のようにマージされることになります。

2つの先頭のデータの小さい方をマージする様子ラスト

図を見ていただければ分かるとおり、この手順でマージを行っていくと、マージ先の集合は2つの集合のデータをソートした結果となります。

これはこの例に限った話ではありません。

この手順でマージを行うと、マージを行う2つの集合がソートさえされていれば、必ずマージ先の集合は2つの集合の全データがソートされた状態になります。

これはいろんなデータで試していただくと実感していただけると思います。

つまり、ソートしたいデータの全体を2つにまず分割し、その分割した各々の集合のデータをソートしてやれば、後は上記の手順で2つの集合のデータをマージすることによりデータ全体をソートすることが可能です。

マージソートはこの考えに則ってデータをソートするアルゴリズムになります。

メモリ量

マージ時にはマージ先となる新たな集合が必要になります

この集合の分、メモリ量が余分に必要になります

クイックソート等のように集合内のデータのみの交換ではソートが行えませんので、これらに比較して必要メモリ量が増加します

分割した集合のソート

では2つに分割した集合はどのようにしてソートすれば良いでしょうか?

マージソートです。

2つに分割した集合にマージソートを行うことでソートを行えば良いです。

下記のようにデータの全体を2つに分割したとしましょう。

分割した集合

それぞれの集合をマージソートでソートすることを考えます。

マージソートとは下記のような考え方のソートでしたね。

  • 集合を中央で2つに分割する
  • 分割後の各集合のデータをそれぞれソートする
  • ソート済みの各集合をマージする

この考え方の通り、まずは各集合は下の図のように2つずつに分割します。

集合の分割

そして分割後の集合をソートします。このソートにもマージソートを用います。

つまり、さらにこの2つの集合を分割することになります。分割してみましょう!

すると、下の図のように各集合に存在するデータが1つになります。

集合の分割

ここで注目していただきたいのが、分割後の各集合内のデータの並びです。

集合内のデータの並び

集合に存在するデータが1つなので実感が湧かないかもしれませんが、集合内のデータは実はソートされていることが分かりますか?各集合内のデータ全体が昇順(or 降順)に並んでますよね?

つまり、データ数が1つの集合は、データが1つなのでソート済みであると考えることできます。

こんな感じで集合に存在するデータが1つになるまでマージソートを繰り返し行うことで、最終的に分割された集合のデータが自動的にソートされることになります。

集合のデータがソートされれば、もうその集合のソートを行う必要はありません。

続いて集合のマージで説明した手順に基づいて「ソート済みの各集合をマージする」が行われることになります。

上の図の8つの集合は下の図のように2つずつマージされて4つの集合にマージされることになります。

集合のマージ

これによりマージ後の4つの集合もソートされたことになりますので、さらにこれらの4つの集合を2つずつマージします。

集合のマージ

これで、最初に分割した2つの集合がそれぞれソートされたことになりますね。

分割後の集合のソート結果

こんな感じで、マージソートを繰り返して集合のデータ数が1つにれば、後はその集合のデータをマージしていくことで最初に分割した集合もソートされることになります。

マージソートのプログラム

ここまで説明してきたマージソートをC言語で実装したプログラムが下記になります。

mergesort.c
#include <stdio.h>
#include <stdlib.h> /* memcpy用 */

/* データの数 */
#define NUM 10

/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
    int i;
    for (i = 0; i < num; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

/* マージソートを行う関数
 * data[] : マージを行うデータの集合
 *         (マージ後のデータの集合を格納)
 * left : マージする1つ目の集合範囲の開始点
 * mid : マージする1つ目の集合の範囲の終了点
 * right : マージする2つ目の集合の範囲の終了点
 * work[] : マージを行うために必要な作業メモリ
 *          (マージ先集合として1時退避先として使用)
 */
void merge(int data[], int left, int mid, int right, int work[]){
    int i, j, k, size;

    /* 1つ目の集合の開始点をセット */
    i = left;

    /* 2つ目の集合の開始点をセット */
    j = mid + 1;

    /* マージ先集合の開始点をセット */
    k = 0;

    /* 2つの集合のどちらかが全てマージ済みになるまでループ */
    while (i <= mid && j <= right) {
        /* マージ済みデータを抜いた2つの集合の
           先頭のデータの小さい方をマージ */
        if (data[i] < data[j]) { 
            work[k] = data[i];
            /* マージした集合のインデックスと
               マージ先集合のインデックスをインクリメント */
            i++;
            k++;
        } else {
            work[k] = data[j];
            /* マージした集合のインデックスと
               マージ先集合のインデックスをインクリメント */
            j++;
            k++;
        }
    }

    /* マージ済みでないデータが残っている集合を
       マージ先集合にマージ */
    while (i <= mid) {
        work[k] = data[i];
        i++;
        k++;
    }
    while (j <= right) {
        work[k] = data[j];
        j++;
        k++;
    }

    /* マージ先集合のサイズを計算 */
    size = right - left + 1;

    /* マージ先集合をdataにコピー */
    memcpy(&data[left], work, sizeof(int) * size);
}

/* マージソートを行う関数
 * data[] : ソートを行うデータの集合
 *          (ソート後のデータの集合を格納)
 * left : ソートを行う範囲の開始点
 * right : ソートを行う範囲の終了点
 * work[] : ソートを行うために必要な作業メモリ
 */
void mergeSort(int data[], int left, int right, int work[]) {
    int mid;


    /* データ数が1の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* 集合を中央で2つに分割する */
    /* left 〜 mid の集合と
        mid+1 〜 right の集合に分割 */
    mid = (left + right) / 2;

    /* 分割後の各集合のデータをそれぞれソートする */
    mergeSort(data, left, mid, work);
    mergeSort(data, mid + 1, right, work);

    /* ソート済みの各集合をマージする */
    merge(data, left, mid, right, work);
}

/* 配列を初期化する関数 */
void initArray(int a[])  {
    a[0] = 5;
    a[1] = 0;
    a[2] = 9;
    a[3] = 7;
    a[4] = 1;
    a[5] = 6;
    a[6] = 3;
    a[7] = 8;
    a[8] = 4;
    a[9] = 2;
}

int main(void)  {
    int array[NUM];
    int work[NUM];

    /* 配列を初期化 */
    initArray(array);

    /* ソート前の配列の表示 */
    printArray(array, NUM);

    /* マージソート */
    mergeSort(array, 0, NUM - 1, work);

    /* ソート後の配列の表示 */
    printArray(array, NUM);

    return 0;
}

スポンサーリンク

プログラムの解説

最後にプログラムの解説を行います。が、ほぼマージソートとはで解説した内容をプログラミングしているだけ&必要な分はコメントを記載していますので、ここではポイントだけ説明しておきます。

mergeSort 関数

mergeSort 関数で主に行っているのはマージソートとはで紹介した下記の3つです。

  • 集合を中央で2つに分割する
  • 分割後の各集合のデータをそれぞれソートする
  • ソート済みの各集合をマージする

この3つは mergeSort 関数内のコメントでも記述していますので、解説と関数の処理を照らし合わせて見ていただければ何をしているのかは理解していただけると思います。

ソートにはマージソートを行っていますので、mergeSort 内でさらに分割した2つの集合に mergeSort 関数を実行しています(再帰呼び出し)。

mergSort関数の再起呼び出し
/* 分割後の各集合のデータをそれぞれソートする */
mergeSort(data, left, mid, work);
mergeSort(data, mid + 1, right, work);

またソートを行うデータ数が1つになった際にはソートが完了したことになりますので、この際には関数の先頭で return を実行して関数を終了するようにしています。

データ数が1の場合の処理
/* データ数が1の場合はソート済みなのでソート終了 */    
if (left == right) {
    return;
}

merge 関数

マージは2つのデータの集合に対し、下記のように処理を行っています。

  • 一方のデータの集合が空になるまでマージを行う
  • 一方のデータが空になったら、他方のデータを、そのデータ順でマージ先集合にコピー

前者を行っているのは下記部分で、

マージの前半処理
/* 2つの集合のどちらかが全てマージ済みになるまでループ */
while (i <= mid && j <= right) {
    /* マージ済みデータを抜いた2つの集合の
       先頭のデータの小さい方をマージ */
    if (data[i] < data[j]) { 
        work[k] = data[i];
        /* マージした集合のインデックスと
           マージ先集合のインデックスをインクリメント */
        i++;
        k++;
    } else {
        work[k] = data[j];
        /* マージした集合のインデックスと
           マージ先集合のインデックスをインクリメント */
        j++;
        k++;
    }
}

後者を行っているのは下記部分になります。

マージの前半処理
/* マージ済みでないデータが残っている集合を
   マージ先集合にマージ */
while (i <= mid) {
    work[k] = data[i];
    i++;
    k++;
}
while (j <= right) {
    work[k] = data[j];
    j++;
    k++;
}

またマージソートでは作業用のメモリが必要になりますので、そのメモリを引数の配列 work として関数に渡しています。

そしてこの配列 work にマージ結果を一旦格納し、最後に data にそのマージ結果をコピーしています。

マージ結果のコピー
/* マージ先集合をdataにコピー */
memcpy(&data[left], work, sizeof(int) * size);

スポンサーリンク

まとめ

このページではマージソートについて解説し、C言語で実装したプログラムの紹介を行いました。

マージソートは下記の3つの処理により実現することができます。

  • 集合を中央で2つに分割する
  • 分割後の各集合のデータをそれぞれソートする
  • ソート済みの各集合をマージする

ポイントは分割後の各集合のデータのソートで、ここにもマージソートを適用することで再帰呼び出しで簡潔にプログラミングすることができます。

マージソートはプログラミングの授業や試験にもよく出題されるアルゴリズムですので、是非このページを参考ににてマスターしておきましょう!

2 COMMENTS

Kちゃん

自分で書いたときにうまく行かなかったのは、「マージ済みでないデータが残っている集合をマージ先集合にマージ」の理解が出来ていないことが原因だったのがわかりました。
ありがとうございます。

返信する
daeu

Kちゃん

コメントありがとうございます。
そして、このページのリクエストありがとうございました!

問題が解決できたのであれば、記事を書いた自分としてはこんなに嬉しいことはないです。
役に立ってよかったです。

また何かリクエストあれば気軽に言ってください!

返信する

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です