今回はマージソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
マージソートとは
まずソートとはデータを並べ替えることをいい、マージソートとは、データをいくつかのグループに分割し、整列と併合を繰り返しながらソートするという方法になります。
たとえば、6,2,7,4,1,5,0,3を昇順に整列するとしましょう。
まず、2つずつのグループに分けます。
6,2 | 7,4 | 1,5 | 0,3
それぞれのグループ内で整列します。
2,6 | 4,7 | 1,5 | 0,3
そしてグループ同士を併合し、4つずつのグループにします。
2,6,4,7 | 1,5,0,3
それぞれのグループ内で整列します。
2,4,6,7 | 0,1,3,5
そしてグループ同士を併合すると、グループは1つだけになりました。
2,4,6,7,0,1,3,5
整列しソート完了です。
0,1,2,3,4,5,6,7
では次は今行った処理を、アルゴリズムを意識して改めて確認したいと思います。
最後の「2,4,6,7」と「0,1,3,5」の併合と整列を例とします。
まずはそのまま併合します。
2,4,6,7,0,1,3,5
前半分の「2,4,6,7」を別の配列(temp)にコピーしておき、
temp と、後半のグループのそれぞれ先頭から順々に比較していきます。
「2,4,6,7」「0,1,3,5」
0の方が小さいため、置き換えます。
↓
0,4,6,7,0,1,3,5
後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,6,7」「0,1,3,5」
1の方が小さいため、置き換えます。
↓
0,1,6,7,0,1,3,5
後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,6,7」「0,1,3,5」
2の方が小さいため、置き換えます。
↓
0,1,2,7,0,1,3,5
temp のデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,6,7」「0,1,3,5」
3の方が小さいため、置き換えます。
↓
0,1,2,3,0,1,3,5
後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,6,7」「0,1,3,5」
4の方が小さいため、置き換えます。
↓
0,1,2,3,4,1,3,5
temp のデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,6,7」「0,1,3,5」
5の方が小さいため、置き換えます。
↓
0,1,2,3,4,5,3,5
後半グループのデータをすべて使用したので、残りは temp のデータで置き換えます。
0,1,2,3,4,5,6,7
これでソートが完了しました。
実装
function mergeSort(array) {
let size = array.length;//ソートする配列の大きさ
let temp = [];//前半グループを一時的に保存しておく配列
let spanSize = 2;//グループのデータ数
while (spanSize <= size) {
let spanIndex = 0;//前半グループの先頭のデータのインデックス
let writeIndex = 0;//書き換え対象のデータのインデックス
while (spanIndex < size) {
let aIndex = spanIndex;//前半グループのデータのインデックス
let bIndex = spanIndex + spanSize / 2; //後半グループのデータのインデックス
for (let i = aIndex - spanIndex; i < bIndex - aIndex; i++) {
temp[i] = array[i + spanIndex];
}
let aYet = true;//前半グループのデータがまだ残っていたら true
let bYet = true;//後半グループのデータがまだ残っていたら true
while (aYet || bYet) {
if (!bYet || (aYet &&
bYet &&
temp[aIndex - spanIndex] <= array[bIndex])) {
array[writeIndex] = temp[aIndex - spanIndex];
aIndex++;
if (aIndex >= spanIndex + spanSize / 2) {
aYet = false;
}
}else{
array[writeIndex] = array[bIndex];
bIndex++;
if (bIndex >= spanIndex + spanSize) {
bYet = false;
}
}
writeIndex++;
}
spanIndex += spanSize;
}
spanSize *= 2;
}
}
let datas = [
6,2,7,4,1,5,0,3
];
mergeSort(datas);
console.log(datas);//0,1,2,3,4,5,6,7と表示
解説
最初の while 文は、spanSize を倍に増やしていくという役割になります。(2つ、4つ、8つ…)
spanSize が size より大きくなったらループを終了します。
while (spanSize <= size) {
...
spanSize *= 2;
}
次の while 文は、ある二組のグループの併合と整列を終えたら次の二組のグループに移るという役割になります。
while (spanIndex < size) {
...
spanIndex += spanSize;
}
次の for 文で、配列 temp に前半グループのデータを保存します。
for (let i = aIndex - spanIndex; i < bIndex - aIndex; i++) {
temp[i] = array[i + spanIndex];
}
次の while 文は、前半グループと後半グループのデータをすべて使い切るまで writeIndex を増やしていき、整列を繰り返すという役割になります。
while (aYet || bYet) {
...
writeIndex++;
}
次の if 分で、前半グループと後半グループのどちらのデータを使用するかを決めます。
「後半グループのデータを全て使い切っている、もしくは前半グループのデータの方が後半グループのデータよりも小さい」場合は前半グループのデータを使い、
それ以外の場合は後半グループのデータを使います。
その後インデックスを1つ増やします。
if (!bYet || (aYet &&
bYet &&
temp[aIndex - spanIndex] <= array[bIndex])) {
array[writeIndex] = temp[aIndex - spanIndex];
aIndex++;
...
}else{
array[writeIndex] = array[bIndex];
bIndex++;
...
}
前半のグループ・後半のグループのデータをそれぞれすべて使い切ったら、aYet、bYet をそれぞれ false にします。
if (aIndex >= spanIndex + spanSize / 2) {
aYet = false;
}
if (bIndex >= spanIndex + spanSize) {
bYet = false;
}
参考書
コメント