4.ソート(バブルソート)

データーを条件で並べ替えてかえます。

[実行結果]

[プログラム]


<script type="text/javascript" charset="Shift_JIS">

   X=new Array(4,2,3,1,5)

   for(A=0;A<5;A++){
      for(B=A+1;B<5;B++){
         if(X[A]>X[B]){	//X[A]のほうがX[B]大きいならば
            BackUp=X[A];	//変数BackUpにX[A]の値をコピーする
            X[A]=X[B];	//X[B]にX[A]の値がはいっている変数BackUpを代入する 
            X[B]=BackUp;	//X[B]に変数BackUpにX[A]の値を
         }
      }
   }

   for(A=0;A<5;A++){	//ソートしたデータを出力
      document.write(X[A]);
   }
</script>

[解説]

今回のソートは前回までやった条件分岐と繰り返し制御をフルに使って行います。 つまりこれが理解できればプログラムの知識がかなりついてきています。

ソートとは並べ替えのことで今回やっているのはバブルソート法です。 ソートには他に選択ソートやクイックソートなどがありますが割合します。

さて解説ですけどバブルソートの流れが下にあるとおりです。 このソートで主なところは2と3です。

  1. ソートをする数値を配列をつかってデーターを入れる
  2. 比較する値と比較される値を決める
  3. 比較する値のほうが小さければ値を交換する
  4. 2〜3を繰り返し処理が終わったその結果を出力

更に細かくバブルソートの流れを見てみましょう。

  1. ソートをする数値のデーターを入れる
    1. 配列をつかってデーターをX[0]〜X[5]に入れる
  2. 比較する値と比較される値を決める
    1. for文の外側の値(Aという変数)を使い,配列X[A]を比較される値とする
    2. for文の内側の値(Bという変数)を使い,配列X[B]を比較する値とする
  3. X[B](比較する値)のほうが小さければX[A](比較される値)と交換する
    1. X[B](比較する値)のほうが小さい
      1. 変数BackUpにX[A]の値をコピーする
      2. X[A]にX[B]の値を代入する
      3. X[B]にX[A]の値がはいっている変数BackUpを代入する
      4. X[B]の値を 1 増やす
    2. X[B](比較する値)のほうが大きい
      1. X[B]の値を 1 増やす
  4. 2〜3を繰り返し処理が終わったその結果を出力
    1. X[0]〜X[5]の中身を出力

1.ソートをする数値のデーターを入れる

1-1.配列をつかってデーターをX[0]〜X[5]に入れる

X=new Array(4,2,3,1,5)配列を使い変数Xにデータを入れています。

2.比較する値と比較される値を決める

2-1.for文の外側の値(Aという変数)を使い,配列X[A]を比較される値とする

for(A=0;A<5;A++) ですが初期値にA=0、条件式には配列に入っているデータの数 5、更新式にはA++を入れます。

2-2.for文の内側の値(Bという変数)を使い,配列X[B]を比較する値とする

for(B=A+1;B<5;B++) ですが初期値にB=A+1、つまりAより 1 大きい値を比較する値とします。条件式には配列に入っているデータの数 5、更新式にはB++を入れます。

3.X[B](比較する値)のほうが小さければX[A](比較される値)と交換する

ここからややこしくなります。

for(B=A+1;B<5;B++){
   if(X[A]>X[B]){ 
      BackUp=X[A];  
      X[A]=X[B];
      X[B]=BackUp;
   }
}

でデータの並べ替えをしているわけですが詳しく A が 0 の時からの流れを見ていきます。

for(B=A+1;B<5;B++)
初期値に A+1 つまり 1 が代入されます。条件式は配列に入っているデータの数の 5 です。

3-1.X[B](比較する値)のほうが小さい

if(X[A]>X[B])
でX[A]とX[B]を比べてX[B]の方が小さい場合はデーターを入れ替えます。

始めは A=0 B=1 です。
つまり最初にX[0]とX[1]を比べるわけです。
X[0]には 4 、X[1]には 2 が入っているわけですがこの場合はX[0]のほうが大きいので入れ替えます。

3-1-1.変数BackUpにX[A]の値をコピーする

BackUp=X[A];変数BackUpにX[0](4)をコピーします。

3-1-2.X[A]にX[B]の値を代入する

X[B]=X[A];次にX[0]にX[1]を入れます。この時点ではX[1]とX[0]共に 2 が入っています。

3-1-3.X[B]にX[A]の値がはいっている変数BackUpを代入する

X[B]=BackUp;ここでX[1]にBackUpに入っていたX[0]の値を入れます。つまり 4 が代入される。

3-1-4.X[B]の値を 1 増やす

ここで内側のループが終わってBの値がひとつ上がって 1 になります。

3-2.X[B](比較する値)のほうが大きい

次はX[0]とX[2]を比べます。 X[0]は入れ替えられたので 2 が入っていて X[2]には 3 が入っています。 この場合はX[0]のほうが小さいので入れ替えは行いません。

Check1 外側のループが一回終わるまでの流れ

次にX[0]とX[3]を比べます。X[0]は 2 、X[3]は 1 です。 X[0]のほうが大きいので入れ替えを行います。 流れは前と同じように変数BackUpにX[0](2)をコピーし、次にX[0]にX[3]を入れます。 最後にX[3]にBackUpに入っていたX[0]の値を入れ 2 が代入される。

この作業が全部で4回繰り返されると内側のループを抜け外のループも一回目を終わります。 この時点でX[0]には一番小さいデータ入っているはずです。

Check2 X[A]の値を 1 増やす

ここで内側のループを抜け、外側のループも一回目を終わります。 そして A の値が 1 上がって 1 になります。 つまり今までX[0]だったのがX[1]になるわけです。

あとはX[1]になった以外は同じ作業の繰り返しです。

4.2〜3を繰り返し処理が終わったその結果を出力

4-1.X[0]〜X[5]の中身を出力
for(A=0;A<5;A++){
   document.write(X[A]);
}

このfor文によってソート(並び替え)された配列の中を書き出しています。 これが結果の出力となります。

Point1 ソート全体の数値の変化

外側のループ 内側のループ A  B X[0] X[1] X[2] X[3] X[4]
    0           0      0   0    4     2     3     1     5	
    1           1      0   1    2     4     3     1     5	X[0]とX[1]を入れ替え
    1           2      0   2    2     4     3     1     5	
    1           3      0   3    1     4     3     2     5	X[0]とX[3]を入れ替え
    1           4      0   4    1     4     3     2     5	
    2           1      1   2    1     4     3     2     5	
    2           2      1   3    1     2     3     4     5	X[1]とX[3]を入れ替え
    2           3      1   4    1     2     3     4     5	
    3           1      2   3    1     2     3     4     5	
    3            2      2   4    1     2     3     4     5	
    4           1      3   4    1     2     3     4     5	
これで流れを整理し、理解をしてください。

どうです、理解できましたか? これが理解できるようになればもうこれからのサンプルも理解できると思います。

はっきりいって自分の中ではソートのプログラムが一番難しいと思っているので^^;


© 2000-2003 Tsukimi / HobbySpace