A little bit of everything

情報系大学院生の備忘録

マージアルゴリズム

マージとは

「併合」という意味で、複数の配列や連結リストなどのデータ列を1つにまとめることをいう。

単純に複数の配列を併合するならば、それぞれの配列の長さを合計した長さ以上の配列を用意し、すべてをそこに格納してしまえばよい(順序など関係なく)。ここでは、複数の整列済み配列をマージし、1つの整列済み配列をつくることを考える。

アルゴリズム

  1. マージする配列をA, Bとする(A,Bはそれぞれ整列済み。マージ後の結果を格納する配列Lを用意する。2 へ。
  2. A, Bの先頭の要素を見て、小さい方の要素をリストから取り出し、Lに追加する。  A, Bどちらかの配列が空になるまで、2 を繰り返す。
  3. 空になっていない方のリストを、先頭から順にすべてLに追加する。

最初の段階。ここからスタート。 f:id:yuukiyg:20160116205551p:plainf:id:yuukiyg:20160116205553p:plainf:id:yuukiyg:20160116205555p:plainf:id:yuukiyg:20160116205601p:plainf:id:yuukiyg:20160116205604p:plainf:id:yuukiyg:20160116205608p:plainf:id:yuukiyg:20160116205611p:plainf:id:yuukiyg:20160116205614p:plainf:id:yuukiyg:20160116205617p:plainf:id:yuukiyg:20160116205620p:plain 完了。