文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第３回【マージソート】
マージソートとは？
合体させまくるソート。
ソート済みの配列同士なら、どっちかの配列のちっちゃい方を順にとってけば、
最終的に合成された配列もソートされてるよね、最初に細かく分割して、
それぞれを上記のように合成してこうっていうのがマージソート。
丁寧にいうと、
- 整列済みのリスト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)); }
