うめすこんぶ

日々のプログラミングで残しておきたいメモ.何かの役に立てれば幸いです.

javascriptでマージソートの勉強

スポンサーリンク

javascriptマージソートやってみました. 最初は,spliceとかで簡単に書けるじゃん!と思ったら, 引数の配列を消してしまうことに気が付きちょっと変更.

マージソート自体のアルゴリズムは簡単なので,コード書くのも楽.

spliceとshiftでマージソート

元の配列を並び替えする場合は x = margeSort(x);と使いましょう.

/**
 * 基本のマージソート ただし,引数xに代入し直しが必要
 * (そのままだと引数の配列が空になってしまう)
 */
function margeSort(x) {
  function marge(x, y) {
    var a  = [];
    while(x.length > 0 && y.length > 0) {
      a.push(x[0] < y[0] ? x.shift() : y.shift());
    }
    return a.concat(x).concat(y);
  }

  if (x.length < 2)  return x;
  return marge(margeSort(x.splice(0, x.length / 2)), margeSort(x));
}

slice多様のマージソート

sliceなので引数にした元配列を犯さない. やはり,x = margeSort(x);と使いましょう. こちらのほうが倍ちかく高速でした.

/**
 * チューニングしたマージソート
 * 配列を空にしない
 */
function margeSort2(x) {
  function marge(x, y) {
    var a  = [], i = 0, j = 0;
    while(i < x.length && j < y.length) {
      a.push(x[i] < y[j] ? x[i++] : y[j++]);
    }
    return a.concat(x.slice(i, x.length)).concat(y.slice(j, y.length));
  }

  if (x.length < 2)  return x;
  var l = x.length / 2;
  return marge(margeSort2(x.slice(0, l)), margeSort2(x.slice(l, x.length)));
}

追記 配列の値が変化しない問題(2014/02/11)

この形式ですと,いちいち配列をソートするのに,x = margeSort(x);とするのは面倒ですね. それならと,margeSortの関数中で

return x = marge(margeSort2(x.slice(0, l)), margeSort2(x.slice(l, x.length)));

などとして引数のxに代入したとしても,関数を出るとxは変化してません. 「javascriptでは引数として与えられた配列は参照型だから関数でいじった結果は関数をでても維持される」と思っていたんですが気のせい. ただし,splice()shift()など,配列を直接弄くるものですと,関数をでても元には戻っていませんでした.直接,x = なんとかでxの参照先を変えようとする方法は意味が無いようです.

margeSort関数内で,配列xにソートされた結果を入れるには,例えば以下のようにします.

function margeSort(x) {
  function marge(a1, a2) {
    //処理
  }

  function sort(x) {
    return ソートされたx
  }

  var a = sort(x); // ソートされたxを代入
  for (var i = 0, l = a.length; i < l; i++) {
    x[i] = a[i]; //引数のxの各要素に値を入れ込む
  }
  return x;
}

一度いじった結果の配列aをつくって,そいつの内容を逐一xに入れる,という俗にいうディープコピーをするコードです.

ここで,

var a = sort(x);
x = a;

とするのはシャローコピーらしいです.この方法では配列xの値が変わることはありません. 関数内でシャローコピーしても,関数をでると,参照先であ1るaが消えてしまうので,結果として,xの値は前の値を参照している状態に戻るみたいです.

プロトタイプにして解決する

いちいちディープコピーするのは計算時間がかかる.ではどうするか. 一つの解決策として,配列操作する場合は

Array.prototype.mergeSort = function() {
  //処理
}

というように書きます. プロトタイプとして書くことで,引数として配列xを入れるのではなく,this[i]のようにthisを使って直接配列の値を変更できるようになります.