クイックソート

最近、Erlang始めたので、手始めに何か適当なアルゴリズムのコードでも書いてみようかと。

まずはソートアルゴリズムの王様クイックソート。小さいのを左に集めて、大きいのを右に集めて、集めたグループ毎にそれぞれ同じよう左右に分けて…これを繰り返していけばソートできるね、というアルゴリズム。理屈は簡単なんだけど、JavaScriptで書くと…

function quickSort(array) {
    _quickSort(array, 0, array.length - 1);   
}
function _quickSort(array, from, to) {
    if (array.length <= 1 ||  from >= to) {
        return;
    }
    var pivot = ((array[from] + array[to]) >> 1);
    var i = from;
    var j = to;
    while( true ) { 
        while (pivot > array[i]) i++;
        while (pivot < array[j]) j--;
        if (i >= j) break;
        var tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
        i++;
        j--;
    }
    _quickSort(array, from, i-1);
    _quickSort(array, j+1, to);
}

こういう一見何をやってるのかさっぱり分かんねぇコードになるわけですが、Erlangで書くと…

quicksort([]) -> [];
quicksort([Head|Tail]) -> 
	quicksort([X || X <- Tail, X < Head ]) ++ [Head] ++ quicksort([X || X <- Tail, X >= Head]).

小さいのを左に集めて、大きいのを右に集めて、繰り返し…、アルゴリズムの説明そのままのコードになる。簡単すぎ。アルゴリズムを理解するという目的であれば、関数型のコードの方が10000倍理解しやすい。

関数型っぽい書き方は、最近のJavaScriptならばサクッと書けますが…

function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }
    var pivot = array.pop();
    var lt = array.filter(function(a){ return a < pivot });
    var ge = array.filter(function(a){ return a >= pivot });
        
    return quickSort(lt).concat([pivot]).concat(quickSort(ge))
}

Arrayオブジェクト作りまくるので効率かなり悪そう。ただ、それ言っちゃerlangでもリスト作りまくるんだけど、気にしなくて良いのかな？