読者です 読者をやめる 読者になる 読者になる

timakin.log

╭( ・ㅂ・)و ̑̑

文系が学ぶコンピューターサイエンス╭( ・ㅂ・)و ̑̑:第3回【マージソート】

マージソートとは?

f:id:u_tis:20150219215448p:plain
合体させまくるソート。
ソート済みの配列同士なら、どっちかの配列のちっちゃい方を順にとってけば、
最終的に合成された配列もソートされてるよね、最初に細かく分割して、
それぞれを上記のように合成してこうっていうのがマージソート

丁寧にいうと、

  • 整列済みのリストAとリストBをマージして整列されたリストCを作る。
  • リストAとリストBの先頭の要素を比較して、小さい方をリストから削除してリストCの末尾に追加する
  • リストA、リストB、どちらか一方の要素がなくなるまで 1. を繰り返す
  • 残った要素をリストCの末尾に順に追加する

って感じ。

分割統治法

こういう"細かく分断して、それぞれの単位で問題を解決して、最終的にでかい問題を解決しよう"って手法を、分割統治法というらしい。
マージソートはその代表例。
破壊と創造。再構築。

マージソートのコード

以下実装。ちなみに計算量はNlogNらしいよ。
マージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるから。

  // MergeSort
  mergeSort: function(items){
    var self = this;

    // 受け取ったdata(配列)が、最小単位になるまで分割し続ける。
    if (items.length < 2) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left    = items.slice(0, middle),
        right   = items.slice(middle);

    return this.merge(self.mergeSort(left), self.mergeSort(right));
  },
  merge: function(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;

    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }

    // 配列で余った一番大きい値を最後にresultに入れて終了。
    return result.concat(left.slice(il)).concat(right.slice(ir));
  }
参考


Computer science in JavaScript: Merge sort | NCZOnline

http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html


マージソート : アルゴリズム

ソートと探索(マージソート)
ALGORITHM NOTE マージソート Merge Sort