JavaScriptでマージソート
- 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 x - y; }; 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でクイックソート
- 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); };
ソートがこんな簡単に書けるものだと思わなかった。最近、アルゴリズム系の話に興味津々。