ソート＃２ マージソート　駆け出しエンジニアのプログラミング講座【C#】

C#プログラミングのアルゴリズム講座をしていきます！

慣れないうちは、あまり頭に入ってこなくて楽しくないかもしれませんので、無理せず学んでいきましょう。

第２回目は、バブルソートよりもう少し実用的な「マージソート」について考えていきたいと思います。

マージソート

マージソートとは

マージソート（Merge Sort）は、安定的なソートが必要な場合に使われることが多いソートです。安定というのは、同じ値がいくつかあっても、最初に配列中に並んでいた順眼が変わらないということです。

同じ値なら入れ替わっても入れ替わらなくても同じように思いますが、順番を変えてしまうと良くない場合があります。

ちょっとわかりにくいですがイメージはレストラン。同じ注文が入った（同じ値）場合、先に入った注文を先にお客さんに出したいので順番を変えてはいけません。このように順番が重要なデータの際に使われることが多いのがこのマージソートになります。

マージソートの動き

step.1 ソート前配列

step.2 2つに分ける

2つに分けることにより、ソートする配列を小さくし簡単にします。

この考え方を「分割統治法」と呼びます。このことについては、記事の後半で説明します。

step.3 分けた配列をソート

step.4 マージする

分けた2つの配列の先頭だけ見て、小さい方を取り続けるという処理をして１つの配列にソートして行きます。この処理のことを「マージ」と言います。

分割統治法

分割統治法（Divide and Conquer）とは、問題をより小さい問題に分割して解決して、その解決した答えを使って元の問題の答えを作り出す方法。

つまり、長い配列より短い配列のがソートが楽なので短くしてソートしようってことです。

マージソートのコード

理論が分かったところで、コードに落としていきましょう！

上記の説明では、配列を２つにしか分けていませんが、以下のコードでは再帰的に分解しているので２つ以上に分けることがあります。

public int[] mergesort(int[] x)
{
    //与えられた配列をマージソート
    mergesort(x, 0, x.Length);
    return x;
}

//配列x内、leftからrightの間をソートする
private void mergesort(int[] x, int left, int right)
{
    //配列の大きさが１以下であればソート終了
    if (right - left <= 1) return;

    // 配列をleftからmid、midからrightの２つに分けてソート
    int mid = left + (right - left) / 2;

    //再帰処理
    mergesort(x, left, mid);
    mergesort(x, mid, right);

    // 配列をマージする
    merge(x, left, mid, right);
}

// マージする処理
private void merge(int[] x, int left, int mid, int right)
{
    int n = right - left;
    int[] work = new int[n];

    // iw:現在処理中の位置を格納
    int iw = 0；
    int iLeft = left;
    int iRight = mid;

    // 2つの配列から、小さい方を選ぶ。同じであれば１つ目の配列から選ぶ
    while(iLeft < mid && iRight < right)
    {
　　　　　// 配列workに値を入れていく
        if(x[iLeft] <= x[iRight])
        {
            work[iw++] = x[iLeft++];
        }
        else
        {
            work[iw++] = x[iRight++];
        }
    }

    //選ばれていない配列の要素を一時的に格納する。
    while(iLeft < mid)
    {
        work[iw++] = x[iLeft++];
    }

    while (iRight < right)
    {
        work[iw++] = x[iRight++];
    }

    // Workからxにコピーする
    System.Array.Copy(work, 0, x, left, n);
}

使い方

// まずサンプルの配列を作成
int[] test = new int[6] { 5, 2, 1, 6, 3, 4 };
//　上記で作成したメソッドを使います。
test = mergesort(test);

以上で、配列testは順番にソートされます。

最後に

バブルソートより複雑なので理解が難しいと思いますが、コードを少しづつ読んで写経して動かして、デバッカーで配列の中身を追いながら勉強すると理解が深まると思います。

もし、わからないところや参考になったところがあればコメントを頂ける嬉しいです。

最後まで読んで頂きありがどうございました。