配列のマージ

Pocket

二つの配列を統合する方法に「マージ」というのがあります。

それぞれの先頭の要素を比べ、小さい方をとります。とった要素は結果用の別の配列に追加します。
とられた配列は先頭の要素が替わります。
またそれぞれの先頭の要素を比べ、小さい方をとります。
これを繰り返します。
いずれどちらかの配列が空になりますので、残った方の配列を結果用の配列にそのまま付け足します。

配列aと配列bをマージして配列cにする場合の例は次の通りです。

配列a 配列b 配列c
1,3,5 2,4,7,6,0
3,5 2,4,7,6,0 1
3,5 4,7,6,0 1,2
5 4,7,6,0 1,2,3
5 7,6,0 1,2,3,4
7,6,0 1,2,3,4,5
1,2,3,4,5,7,6,0

これをJavaScriptで行うためのサンプルは次の通りです。

function merge(a,b){
  c=new Array();
  while(a.length>0 && b.length>0){
    c.push(a[0]<b[0] ? a.shift() : b.shift());
  }
  return(c.concat(a).concat(b));
}

[ 2011年12月8日 | カテゴリー: JavaScript | タグ: , ]

« | »

コメント

  1. […] 配列の要素が1個の場合はその配列を返す。 配列の要素が2個以上の場合は配列を前半と後半に2等分する(奇数の場合は中央の要素をどちらかに含める)。 前半の配列をマージソートする。 後半の配列をマージソートする。 前半と後半の配列をマージする。 ※配列のマージを参照。 […]

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報