JavaScriptでクイックソート / LiosK-free Blog

JavaScriptでクイックソート

2007-11-05
カテゴリ: Client Side
タグ: Tips JavaScript 安易な発想アルゴリズムソート

Haskellでのクイックソートを参考に、JavaScriptで単純なクイックソートを行う関数を書いた。

第一引数にはソートする配列を渡して、第二引数には比較関数を渡す。比較関数はArray.prototype.sortに渡す関数と同じ。

var sort = function(list, comparer) {
    if (!comparer) comparer = function(x, y) { return y - x; };
    return (function s(l) {
        var len = l.length;
        if (len < 2) return l;
        var x = l[0], y = l[1], lt = [], gt = [];
        for (var i = 1; i < len; y = l[++i]) (comparer(x, y) < 0 ? lt : gt).push(y);
        return s(lt).concat([x], s(gt));
    })(list);
};

ソートがこんな簡単に書けるものだと思わなかった。最近、アルゴリズム系の話に興味津々。