読者です 読者をやめる 読者になる 読者になる

マージソート

次はマージソートマージソートは要素を半分ずつ分け、半分にしたものをさらに分ける、これを全部ばらばらになるまで繰り返して、結合する。結合する時に互いの先頭を比較して小さいのから取り出していくことでソートするというアルゴリズム。

例によって、まずJavaScriptで書くと…

function mergeSort(array) {
    var len = array.length;
    if (len <= 1) return array;
    var n = len >> 1;
    return merge(mergeSort(array.slice(0, n)), mergeSort(array.slice(n)));
}

function merge(a, b) {
    var r = [];
    while(a.length && b.length) {
        r.push( a[0] <= b[0] ? a.shift() : b.shift());
    }
    return r.concat(a).concat(b)
}

Erlangで書くと…

mergesort([]) -> [];
mergesort([X]) -> [X];
mergesort(List) -> 
    N = length(List) div 2,
    {A, B} = lists:split(N, List),
    merge(mergesort(A), mergesort(B)).

merge(X, []) -> X;
merge([], X) -> X;
merge([Ha|Ta], [Hb|Tb]) when Ha > Hb ->
    [Hb] ++ merge([Ha|Ta], Tb);
merge([Ha|Ta], [Hb|Tb])  ->
    [Ha] ++ merge(Ta, [Hb|Tb]).

Erlangでも変わらんですね。ただしJavaScriptで pop とか shift とか配列にあるまじきメソッドを禁止すると、mergeが倍ぐらいに長くなります。

function merge(a,b) {
    var result = [];
    var ia = 0, ib = 0, ir = 0;
    while(ib < b.length && ia < a.length) {
        if (a[ia] > b[ib]) {
            result[ir++] = b[ib++];
        } else {
            result[ir++] = a[ia++];
        }
    }
    while(ia < a.length) result[ir++] = a[ia++];
    while(ib < b.length) result[ir++] = b[ib++];
    return result;
}

JavaやCで書く場合はこういう感じになるでしょう。

ガード

when なんたらという部分はガード条件という。

merge([Ha|Ta], [Hb|Tb]) when Ha > Hb ->
    [Hb] ++ merge([Ha|Ta], Tb);
merge([Ha|Ta], [Hb|Tb])  ->
    [Ha] ++ merge(Ta, [Hb|Tb]).

Erlangではパターンマッチで呼び出される関数をディスパッチできるんですが、同じパターンにマッチしても値が特定の条件を満たしていればこっち、みたいな指定ができて、その指定をガードという。

関数内部で普通に条件分岐してもいい。

merge([Ha|Ta], [Hb|Tb]) ->
    if 
       Ha > Hb  -> [Hb] ++ merge([Ha|Ta], Tb);
       true     -> [Ha] ++ merge(Ta, [Hb|Tb])
    end.

このifの条件もやっぱりガードと呼ばれるらしい。Erlangにはelseが無いので「true」というガードを指定して全て適用とするそうだ。