タグ: ソート

JavaScriptでマージソート

以前、JavaScriptでクイックソートを書いてみたことがあったが、今度はマージソートを書いてみた。

var sort = function self(list) {
    if (list.length < 2) return list;
    var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
    while (left.length && right.length)
        list.push(left[0] <= right[0] ? left.shift() : right.shift());
    return list.concat(left, right);
};

比較関数を使う場合は↓

var sort = function(list, comparer) {
    if (!comparer) comparer = function(x, y) { return x - yy - x; };
    return (function self(list) {
        if (list.length < 2) return list;
        var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
        while (left.length && right.length)
            list.push(comparer(left[0], right[0]) <>= 0 ? left.shift() : right.shift());
        return list.concat(left, right);
    })(list);
};

意外とシンプルなんだなー

[追記 (2011-06-29)]

安定ソートになっていなかったので一部ソースを修正。Thanks, id:escape_artist!

[追記 (2011-07-03)]

比較関数の定義がECMAScriptのsort関数と逆になっていたので一部修正。
スポンサーサイト



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);
};

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