クイックソートをjavascriptsで書いてみた

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミングを最近読んでいます．勉強がてらクイックソートをjavascriptで 実装してみました．

配列バージョン

function qSort(x) {
  function partition(l, u) {
    if (l >= u) return; // 長さ1なら終わり
    
    var t = x[l], m = l;
    // tは基準値，mはt未満のグループの最後のインデックスを常に指す
    
    for (var i = l + 1; i <= u; i++) {
      if (x[i] < t) { 
        var temp = x[i]; //swap
        x[i] = x[++m];
        x[m] = temp;
      }
    }
    
    var temp = x[m]; //swap
    x[m] = x[l];
    x[l] = temp;

    partition(l, m - 1);
    partition(m + 1, u);
  }
  
  partition(0, x.length - 1);
  return x;
}

リストバージョン

クイックソートをリスト形式で書いたものです．haskellだとすごく簡単に書けるのですが， javascriptだと9行もかかります． しかも，上の配列バージョンよりかなり遅いです．

function qSortList(x) {
  if (x.length < 1) return x; // リストが空ならすぐ終わり
  var a = [], b = []; // aにx[0]より小さいもの，bにそれ以外のものを分配
  for (var i = 1; i < x.length; i++) {
    if (x[i] < x[0]) a.push(x[i]);
    else b.push(x[i]);
  }
  return qSortList(a).concat(x[0]).concat(qSortList(b)); //a + x[0] + bの結合
}