トランプその6

マージソート

併合処理を繰り返して並べ替えをするマージソートについて実装してみます。
今回のプログラムは基本情報技術者平成22年春期のアルゴリズム問題を参考に実装します。
元の問題と見比べて参考にしてみてください。

HTMLの修正

今回はデータが多い方がソートの効果が出やすいので、元のカードの並び替えるように実装します。
ソートボタンを開始ボタンの隣に追加できるように以下の行を追加しておきましょう。

<INPUT TYPE="button" NAME="cmdSort" value="ソート" onclick="startsort()">           

startsort()が今回のプログラムの始まりです、

併合処理の修正

前回の併合処理では、HIGH-VALUEを使って終了判定をしていました。
マージソートの実装ではHIGH-VALUEを使いにくいので、違う手法を採用します。

最初はHIGH-VALUEがあるパターンと同じです。
カードを比べて、小さい方を出して行きます。
この場合は1と3の比較で1が出されました。

続いて2,3の比較で2が出されました。

続いて3,5の比較で2が出されました。

続いて4,5の比較で2が出されました。

続いて4,5の比較で2が出されました。

HIGH-VALUEがありませんので、この場合は比較対象がありません。
こうなる直前に比較をやめる必要があります。

繰り返しの条件は、HIGH-VALUEがある場合とは変わってきます。
この場合は、
「どちらかのカードが無くなった時」終わります。
繰り返すための条件に言い換えると、
「どちらのカードもまだある時」繰り返します。

しかし、ここで終了するとカードが残ってしまいます。
どちらかのカードがまだ余っていますので、それらを全て出し終われば終了です。

以下にコメントとともにソースコードを示します。
merge2()として前回のmerge()とは別に作ります。

slist1とslist2は配列として受け取ります。
num1,num2はそれぞれのサイズです。
マージした結果はlistという配列に受け取ります。

function merge2(slist1,num1,slist2,num2,list)
{
   var i,j;
   i=0;
   j=0;
   while(i<num1 && j<num2) {  // i,j両方のカードがまだある間繰り返す。
       if( slist1[i].num < slist2[j].num ) {  // slist1のカードが小さい場合
           list[i+j] = slist1[i];     // listに入れて
           i=i+1;                     // slist1を進める
       } else {                                // slist2のカードが小さい場合
           list[i+j] = slist2[j];     // listに入れて
           j=j+1;                     // slist2を進める
       }
   }
   // ここまでで、どちらかのカードが無くなっている
   while(i<num1 || j<num2 ) {  // どちらかがまだ無くなっていない間繰り返す
       if( i<num1 ) {   // slist1がまだ残っている場合
           list[i+j] = slist1[i];   // slist1のカードをlistに入れて
           i=i+1;                   // slist1を進める
       } else {        // slist2がまだ残っている場合
           list[i+j] = slist2[j];   // slist2のカードをlistに入れて
           j=j+1;                   //slist2を進める
       }
   }    
}

前回のマージと違い、表示領域ではなく配列に併合していきます。
未だここまででは、結果には現れませんが、実行してみて動作確認はしておきましょう。
今までのプログラムも動かなくなっていたら、何か間違えているのでここで修正します。

マージソートの仕組み

併合処理を利用してマージソートは出来ています。
併合処理の前提は、「それぞれが既に並び変わっている」ことです。
最初は、全く並び変わっていないことが想定されるので、半分ずつに分割していきます。
最終的に分割したものが1枚になれば、その組は並んでいると見なせます。

分割が終了してから併合を開始します。
分割された部分から順次並び変わります。
それぞれが並び変わったら併合処理を繰り返していくと、最後には全て並び変わった状態になります。

仕組みが分かったところで実装します。

function mergesort(list,num)
{
      ここにプログラムを書く
}

list は並び替えたい配列。numはその大きさを受け取ってきます。

内部で使う配列を宣言します。

var slist1=[];   //分割する片方の配列
var slist2=[];   //分割するもう一方の配列
var num1;    // slist1の大きさ
var num2;    // slist2の大きさ
var i;      //ループ用の変数

まず、1個のデータしか残っていない場合は並び替えようが無いので、何もしません。
2個以上のデータの場合は、並び変わる可能性があります。

if(num>1) { // 2個以上なら処理をする
　　　ほかのプログラムはさらにこの中に書く
}

分割するサイズを計算します。

 num1=Math.floor(num/2);  //全体の半分にしますが、端数は切り捨てます。
 num2=num-num1;           //全体から残り半分の大きさを計算します。

これにより、例えばnumが7個の場合は3個と4個に分割されます。

分割処理を行います。単純にnum1個のデータをlistから slist1にコピーしています。

for(i=0;i<num1;i++) {
     slist1[i]=list[i];
}

分割処理その2です。先ほどnum1番目まで終わりましたからその続きからコピーします。
コピーする数はnum2です。

 for(i=0;i<num2;i++) {
     slist2[i]=list[num1+i];
 }

次が、このマージソートの肝になる部分です。
再帰呼び出しという手法を用いています。自分自身がプログラムを呼び出しています。
分割したそれぞれについてマージソートを行うように命令を出します。

  mergesort(slist1,num1);    // 前半部分をマージソート
  mergesort(slist2,num2);　　// 後半部分をマージソート
  merge2(slist1,num1,slist2,num2,list);     // 前半と後半は並び変わったので、それを併合する

最後に仕上げです。
最初にHTMLで作成したボタンはstartsort()という関数を呼び出します。
ここで最終結果を表示するために dispCard()を呼び出します。

function startsort()
{
    mergesort(cards,cardcnt);   // カードをマージソートする
    dispCard();   // カードの表示
}