マージソート

アルゴリズム入門

マージソートは、リスト（ArrayListなど）を分割していき、分割された要素をマージ（結合）していく事でソートを行うアルゴリズムです。


リストの要素はバラバラに分割されますが、バラバラになった要素は隣同士を大小比較しながら結合（マージ）します。
すると２つの要素を持つソートされたリストが作成されます。
次にそれらのリストを２つ選択し、結合（マージ）します。
この時、それぞれのリストはそれぞれ既にソート済である事がポイントです。

このように図で書くとわかりますが、隣り合ったリストを比較する時は事前にソートされたリスト同士のソートになる為、非常に綺麗な形でマージされます。
尚、この例では綺麗に２分割されていますが、綺麗に分割されなくとも同じです。
イメージとしてはトーナメント表のシードのような扱いになるだけです。

MergeSort

マージソートをプログラムで表現する為にはマージ（結合）だけではなく、分割も組み込まなければなりません。

package example06;

import java.util.ArrayList;

public class MergeSort extends AbstractSort
{
    // マージソート
    public void sort()
    {
        mergeSort(bookList);
    }
    // マージソート
    private void mergeSort(ArrayList list) {
        // 再帰呼び出しの終了
        int size = list.size();
        if(size == 1) {
            return;
        }
        // ２つのArrayListに分割
        ArrayList left = new ArrayList();
        ArrayList right = new ArrayList();
        int mid = size / 2;
        for (int i = 0; i < size; i++) {
            if(i < mid) {
                left.add(list.get(i));
            } else {
                right.add(list.get(i));
            }
        }
        // 再帰呼び出し
        mergeSort(left);
        mergeSort(right);
        // マージ
        list.clear();
        int indexL = 0;
        int indexR = 0;
        while(indexL < left.size() && indexR < right.size()) {
            Book bookL = (Book) left.get(indexL);
            Book bookR = (Book) right.get(indexR);
            if(bookL.getPrice() <= bookR.getPrice()) {
                list.add(bookL);
                indexL++;
            } else {
                list.add(bookR);
                indexR++;
            }
        }
        while(indexL < left.size()) {
            list.add(left.get(indexL++));
        }
        while(indexR < right.size()) {
            list.add(right.get(indexR++));
        }
    }
}

このプログラムのポイントは再帰呼出にあります。

再帰呼び出し

再帰呼び出しはプログラムのテクニックの１つで、メソッドの処理で自分のメソッドを呼び出す処理です。
再帰呼び出しも繰り返し処理の１つですが、処理がツリー構造のようにネストしており、その深さが可変であるような場合に使用されます。
しかし、再帰呼出を行う場合は無限ループにならないように充分に注意しなくてはならなりません。


階乗計算を使い簡単な例を示します。

    public int fact(int n) {
        if(n == 1) {
            return 1;
        }
        return fact(n) * n;
    }

階乗計算とは、ある数ｎに対して、1 * 2 * 3 * … * (n-1) * n の値を求めることです。
したがって、引数nが与えられたならば、n-1までの階乗計算を行い、その結果にnを掛けて返すと考えることができます。
これを再帰的に繰り返していくと、nは徐々に小さくなっていくでしょう。
しかし、どこかで止めない限りはマイナスに突入して、意図しない結果を返してしまいます。
そこで、nが1となった時点でストップするようにif文が記述されているのです。


しかし、階乗計算であればfor文を用いて記述することも当然ながら可能です。

    public int fact(int n) {
        int result = 1;
        for(int i = 1; i <= n; i++) {
            result = result * n;
        }
        return result;
    }

この２つの実装はどちらも間違ってはいません。
階乗計算に限って言うのであれば、後者のforループでも問題がないため、解り易い実装を取ることも重要かと思います。
ただし、再帰呼び出しを行った方が読みやすくなるのであれば、再帰呼び出しを検討するべきです。

mergeSort(ArrayList)

このメソッドでは大きく３つの処理が行われています。


１つ目は、引数で与えられたArrayListを２つのArrayListに分割することです。
leftとrightという事で、前半分のArrayListと後半分のArrayListに分割されます。
ここでArrayListが綺麗に２分割される必要はありませんが、おおよそ半分づつに分割されます。


２つ目の処理は分割した２つのArrayListに対して、再帰呼び出しによるマージソートを行います。
この再帰呼び出しは、ArrayListがソート不要になるまで、すなわちサイズが1となるまで繰り返されます。
つまり、メソッドの最初に記述されたif文が再帰呼び出しの終了条件を表します。


３つ目の処理は、２つのArrayListをマージして元のArrayListに詰めなおす処理です。
それぞれのArrayListは既にソートされている為、比較する時はそれぞれの先頭要素を比較すれば充分である事に注意してください。
最初のループではどちらかの要素がなくなるまで比較し続けており、残ったArrayListの要素はそのままの順番で後ろに追加されています。


このようにマージソートでは再帰呼び出しを使うことで、分割と結合を上手く処理することができます。
頭の中に処理の流れがイメージできない場合は、ArrayListの要素が１つの時、２つの時、３つの時・・・と順に考えてみましょう。