今回はマージソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
マージソートとは
まずソートとはデータを並べ替えることをいい、マージソートとは、データをいくつかのグループに分割し、整列と併合を繰り返しながらソートするという方法になります。
たとえば、６，２，７，４，１，５，０，３を昇順に整列するとしましょう。
まず、２つずつのグループに分けます。
６，２ ｜ ７，４ ｜ １，５ ｜ ０，３
それぞれのグループ内で整列します。
２，６ ｜ ４，７ ｜ １，５ ｜ ０，３
そしてグループ同士を併合し、４つずつのグループにします。
２，６，４，７ ｜ １，５，０，３
それぞれのグループ内で整列します。
２，４，６，７ ｜ ０，１，３，５
そしてグループ同士を併合すると、グループは１つだけになりました。
２，４，６，７，０，１，３，５
整列しソート完了です。
０，１，２，３，４，５，６，７
では次は今行った処理を、アルゴリズムを意識して改めて確認したいと思います。
最後の「２，４，６，７」と「０，１，３，５」の併合と整列を例とします。
まずはそのまま併合します。
２，４，６，７，０，１，３，５
前半分の「２，４，６，７」を別の配列（temp）にコピーしておき、
temp と、後半のグループのそれぞれ先頭から順々に比較していきます。
「２，４，６，７」「０，１，３，５」
０の方が小さいため、置き換えます。
↓
０，４，６，７，０，１，３，５
後半グループのデータを使用したのでインデックスを１つ進め、続けて比較します。
「２，４，６，７」「０，１，３，５」
１の方が小さいため、置き換えます。
↓
０，１，６，７，０，１，３，５
後半グループのデータを使用したのでインデックスを１つ進め、続けて比較します。
「２，４，６，７」「０，１，３，５」
２の方が小さいため、置き換えます。
↓
０，１，２，７，０，１，３，５
temp のデータを使用したのでインデックスを１つ進め、続けて比較します。
「２，４，６，７」「０，１，３，５」
３の方が小さいため、置き換えます。
↓
０，１，２，３，０，１，３，５
後半グループのデータを使用したのでインデックスを１つ進め、続けて比較します。
「２，４，６，７」「０，１，３，５」
４の方が小さいため、置き換えます。
↓
０，１，２，３，４，１，３，５
temp のデータを使用したのでインデックスを１つ進め、続けて比較します。
「２，４，６，７」「０，１，３，５」
５の方が小さいため、置き換えます。
↓
０，１，２，３，４，５，３，５
後半グループのデータをすべて使用したので、残りは temp のデータで置き換えます。
０，１，２，３，４，５，６，７
これでソートが完了しました。
実装
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 を倍に増やしていくという役割になります。（２つ、４つ、８つ…）
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 分で、前半グループと後半グループのどちらのデータを使用するかを決めます。
「後半グループのデータを全て使い切っている、もしくは前半グループのデータの方が後半グループのデータよりも小さい」場合は前半グループのデータを使い、
それ以外の場合は後半グループのデータを使います。
その後インデックスを１つ増やします。
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;
}
参考書
コメント