トランプその4

このページではカードの並べ替えを行うアルゴリズムについて学びます

準備

HTMLとCSSを準備します。
トランプその3で作成したプログラムをForkしましょう。

HTML

<html>
   <body>
       <form name="form1">         
           <br>
            <INPUT TYPE="button" NAME="cmdCalc" value="開始" onclick="start()">           
       </form>        
　    
   <div id="disp">
        </div>
	<form name="form2">
        <INPUT TYPE="button" NAME="cmdGet" value="カードをもらう" onclick="getcard()">                    
        <INPUT TYPE="button" NAME="cmdPut" value="カードを返す" onclick="putcard()">                    
　
        <br> 
       どのマーク？（0:♠,1:♣, 2:♥, 3:♦）<INPUT TYPE="text" NAME="txtA"><br>
       どの数字？(1～13)<INPUT TYPE="text" NAME="txtB"><br>
        <INPUT TYPE="button" NAME="cmdPut2" value="指定したカードを返す" onclick="putcard2()">           
         <INPUT TYPE="button" NAME="cmdSort1" value="並べ替え１" onclick="mycardsort1()">           
        <INPUT TYPE="button" NAME="cmdSort2" value="並べ替え２" onclick="mycardsort2()">           
     </form>
       <div id="disp2">
        </div>
  </body>
</html>

トランプその3で作成したHTMLにボタンをいくつか追加しています。

mycardsort1() 並び替え1ボタン用のプログラム
mycardsort2() 並び替え2ボタン用のプログラム

バブルソート

まずはソート（並び替え）の基本中の基本であるバブルソートについて学びます。
常に隣同士を比較して、順番が逆だったら交換するという処理を繰り返します。

これで1周目完了です。
1周目が完了すると、右端には一番大きな数のカードがあるはずです。
続いて2周目です。2周目は、右端に既に確定したカードを除外して繰り返し回数が少なくなります。

残ったカードの中で一番大きな数のカードが右端にあります。ここまでで、大きい2枚のカードが確定しています。
続いて3周目も、既に確定したカードを除いて処理します。

残ったカードの中で一番大きな数のカードが右端にあります。ここまでで、大きい3枚のカードが確定しています。
続いて4周目も、既に確定したカードを除いて処理します。

残ったカードの中で一番大きな数のカードが右端にあります。ここまでで、大きい4枚のカードが確定しています。
続いて5周目も、既に確定したカードを除いて処理します。

5周目は、最後の2枚のカードなので、1回比較して終了です。
これで、全てのカードが並び変わっているはずです。

コーディング

では、バブルソートのプログラムを完成させていきます。

HTMLのボタンかmycardsort1()という関数を呼び出すことになっていますから、その名前から始めます。

function mycardsort1()
{
　//ここにプログラムを書く
}

変数の宣言をしておきましょう。

var i,j,w;

まずは1周目のプログラムを実装します。
隣同士を比較して、順番が逆順だったら交換です。
繰り返しの回数は、右隣まで比較することを考慮しカード枚数より一回少なく繰り返します。

for(j=0;j<mycardcnt-1;j++) {
   if(mycards[j].num>mycards[j+1].num) {
       w = mycards[j+1];
       mycards[j+1]=mycards[j];
       mycards[j]=w;
   }          
}

最後に表示関数を呼び出しましょう。

dispMyCard();

このプログラムの段階で、実行結果を確認しておきましょう。
並べ替えはまだ終了しませんが、右端には一番大きいカードがあれば正しいプログラムです。
ちなみにこの状態でも、たくさんボタンを押せばどんどんならび変わるはずです。

練習

このプログラムを改造して、バブルソートを完成させてみましょう。
- さらに変数iの繰り返しを追加します。繰り返しの初期値は0、終了はmycardcnt-1です。
- 内側のループはこのままでも並び変わりますが、より効率よく不必要な繰り返しをしないために内側の条件を変更します。
  - 最初はmycardcnt-1回、次はmycardcnt-2回、…、最後は何回繰り返すのが効率よいでしょうか。

挿入ソート

基本ソートの一種である挿入ソートを実装します。

挿入ソートの実装前に少し準備をしておきます。
HTML

<html>
   <body>
       <form name="form1">         
           <br>
            <INPUT TYPE="button" NAME="cmdCalc" value="開始" onclick="start()">           
       </form>        
　    
   <div id="disp">
        </div>
	<form name="form2">
        <INPUT TYPE="button" NAME="cmdGet" value="カードをもらう" onclick="getcard2()">                    
        <INPUT TYPE="button" NAME="cmdPut" value="カードを返す" onclick="putcard()">                    
　
        <br> 
       どのマーク？（0:♠,1:♣, 2:♥, 3:♦）<INPUT TYPE="text" NAME="txtA"><br>
       どの数字？(1～13)<INPUT TYPE="text" NAME="txtB"><br>
        <INPUT TYPE="button" NAME="cmdPut2" value="指定したカードを返す" onclick="putcard2()">           
         <INPUT TYPE="button" NAME="cmdSort1" value="並べ替え１" onclick="mycardsort1()">           
        <INPUT TYPE="button" NAME="cmdSort2" value="並べ替え２" onclick="mycardsort2()">           
     </form>
       <div id="disp2">
        </div>
  </body>
</html>

一部だけ変更します。カードをもらう処理を少し変更しますので、HTMLでgetcard()→getcard2()とします。

続いてgetcard2()を完成させます。
これまで使って来たgetcard()は自分のカードの先頭に入れていましたが、自分のカードの最後に追加するように変更します。

function getcard2()
{
   var c;
   var i;
   
    if( cardcnt>0 ) {
     c = cards[0]; 
     for(i=0;i<cardcnt;i++) {
     	cards[i]=cards[i+1];   
     }
     cardcnt--;
     //  ↑ここまでは、変更無し。
     //　↓ここから自分のカードに追加
     mycards[mycardcnt]=c;
     mycardcnt++;
     //  ↑変更ここまで
  
     dispCard();
     dispMyCard();
    }
}

ここまでで動作確認しておきましょう。
手札を貰った時に、最後に追加されるようになれば準備完了です。

挿入のアルゴリズム

既に順番に並んでいるところへ、適当な場所へ挿入するためのアルゴリズムです。
挿入ソートに進むための基本です。

後ろから順に自分が入るべき位置を探します。
判断基準は、自分のカードより大きければまだ前へ、自分のカードより大きなカードを見つけてその場所へ移動します。

HTMLのボタンからmycardsort2()という関数を呼び出すことになっていますから、その名前から始めます。

function mycardsort2()
{
　//ここにプログラムを書く
}

変数の宣言をしておきましょう。

var i,j,w;

一番後ろのカード(mycardcntが枚数なので、最後の番号はmycardcnt-1）を退避しておきます。

w = mycards[mycardcnt-1];

退避したカードのさらに1枚前から開始して、w.num が小さい間一枚ずつずらします。
また、最後まで見つからない場合もあるので j>=0 で繰り返せる条件を追加します。

for(j=mycardcnt-2;j>=0 && mycards[j].num>w.num ;j--) {
  mycards[j+1]=mycards[j];
}

最後に、退避してあったカードを空いた場所へ格納します。

 mycards[j+1]=w;

最後に表示関数を呼び出しましょう。

dispMyCard();

ここまでのプログラムです。
動作確認して挿入の動きを確認しておきましょう。

2枚カードをもらう
挿入する
1枚カードをもらう
挿入する

の3,4を繰り返すだけでも、並べ替えが完了することも確認しましょう。

挿入ソートへ拡張

まずは2枚で挿入して順番通りにする。
続いてその2枚に後ろの1枚を挿入して3枚が順番通りになる。
さらに続いて3枚に後ろの1枚を挿入して4枚が順番通りになる。
これをカードが有る限り続けると、全て並び変わることになります。

練習

このプログラムを改造して、挿入ソートを完成させてみましょう。
- 外側のループは1からmycardcntより小さい間繰り返します。
- 内側のループのどこに外側のループの変数を反映させるかがポイントです。退避するカードと最初のjの値をどう表すかを考えましょう。

「トランプその4」をウィキ内検索

最終更新：2013年01月29日 00:50

添付ファイル

JavaScriptで学ぶアルゴリズム講座

メニュー

リンク