LiosK-free Blog

• 2007-11-28
• カテゴリ: Client Side
• タグ: Tips 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 y - 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);
};

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

• パーマリンク
• コメント (0)
• トラックバック (0)
• 
• 

http://liosk.blog103.fc2.com/tb.php/58-d02ad21b