二つの配列を統合する方法に「マージ」というのがあります。
それぞれの先頭の要素を比べ、小さい方をとります。とった要素は結果用の別の配列に追加します。
とられた配列は先頭の要素が替わります。
またそれぞれの先頭の要素を比べ、小さい方をとります。
これを繰り返します。
いずれどちらかの配列が空になりますので、残った方の配列を結果用の配列にそのまま付け足します。
配列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));
}
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));
}
コメント
[…] 配列の要素が1個の場合はその配列を返す。 配列の要素が2個以上の場合は配列を前半と後半に2等分する(奇数の場合は中央の要素をどちらかに含める)。 前半の配列をマージソートする。 後半の配列をマージソートする。 前半と後半の配列をマージする。 ※配列のマージを参照。 […]