【JavaScriptでアルゴリズム】並び替え(マージソート)

アルゴリズム

今回はマージソートのアルゴリズムについて、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」の併合と整列を例とします。

まずはそのまま併合します。
,4,6,7,0,1,3,5


前半分の「2,4,6,7」を別の配列(temp)にコピーしておき、
temp と、後半のグループのそれぞれ先頭から順々に比較していきます。


,4,6,7」「,1,3,5」

0の方が小さいため、置き換えます。

,4,6,7,0,1,3,5


後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
,4,6,7」「0,,3,5」

1の方が小さいため、置き換えます。

0,,6,7,0,1,3,5


後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
,4,6,7」「0,1,,5」

2の方が小さいため、置き換えます。

0,1,,7,0,1,3,5


temp のデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,,6,7」「0,1,,5」

3の方が小さいため、置き換えます。

0,1,2,,0,1,3,5


後半グループのデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,,6,7」「0,1,3,

4の方が小さいため、置き換えます。

0,1,2,3,,1,3,5


temp のデータを使用したのでインデックスを1つ進め、続けて比較します。
「2,4,,7」「0,1,3,

5の方が小さいため、置き換えます。

0,1,2,3,4,,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;
          }





参考書

コメント

コンタクトフォーム

    タイトルとURLをコピーしました