●バブルソートは、最小値を求めることをせずに、左から順に隣会った左右のデータを比べ、左側のデータが大きい時にはすぐに入れ換えを行なう方法です。バブルとは泡を意味していて、泡が浮くように小さな(プログラムの組み方で大きな)データが集まるように並べ換えが行なわれることからこう呼ばれている。
●次のような数字で実際にやってみます。
●まず、1番と2番を比べます。52と42で大きいのは52の方です。交換します。
52 46 24 12 15 35 18 56 63 23
●次に、2番と3番を比べます。52と24で大きいのは52の方です。交換します。
46 52 24 12 15 35 18 56 63 23
●次に、3番と4番を比べます。52と12で大きいのは52の方です。交換します。
46 24 52 12 15 35 18 56 63 23
●次に、4番と5番を比べます。52と15で大きいのは52の方です。交換します。
46 24 12 52 15 35 18 56 63 23
●次に、5番と6番を比べます。52と35で大きいのは52の方です。交換します。
46 24 12 15 52 35 18 56 63 23
●次に、6番と7番を比べます。52と18で大きいのは52の方です。交換します。
46 24 12 15 35 52 18 56 63 23
●次に、7番と8番を比べます。52と56で大きいのは56の方です。交換しません。
46 24 12 15 35 18 52 56 63 23
●次に、8番と9番を比べます。56と63で大きいのは63の方です。交換しません。
46 24 12 15 35 18 52 56 63 23
●次に、9番と10番を比べます。63と23で大きいのは63の方です。交換します。
46 24 12 15 35 18 52 56 63 23
●次に、9番と10番を比べます。63と23で大きいのは63の方です。交換します。
46 24 12 15 35 18 52 56 23 63
●これで最後まできました。これまでの操作で一番大きい63が最後に来ました。10番はこれで確定です。さらにまだ完成していない1番から9番までについて作業をつづけます。
●2回目は1番から9番までについて作業します。
●1番と2番を比べます。46と24で大きいのは46の方です。交換します。
46 24 12 15 35 18 52 56 23 63
●2番と3番を比べます。46と12で大きいのは46の方です。交換します。
24 46 12 15 35 18 52 56 23 63
●3番と4番を比べます。46と15で大きいのは46の方です。交換します。
24 12 46 15 35 18 52 56 23 63
●同様に9番までやっていきます。説明は省略します。2回目の最後にはこのようになります。
24 12 15 35 18 46 52 23 56 63
●3回目は1番から8番までについて作業します。
●また1番と2番から比べますが、途中省略して最後だけ示します。
12 15 24 18 35 46 23 52 56 63
●4回目は1番から7番までについて作業します。
12 15 18 24 35 23 46 52 56 63
●これを繰り返すことで、1番から2番まで作業することになり、2番まで確定すれば、全部が並べ替えられたことになります。
12 15 18 24 23 35 46 52 56 63 …5回目
12 15 18 23 24 35 46 52 56 63 …6回目
●2番目の確定を待たずに途中で並び替えが完成してしまうことがあります。この場合も6回目で5番目が確定したらできあがっています。コンピュータが並び替えが完成したと判断して無駄な作業を省くことも考える必要がありそうです。
12 15 18 23 24 35 46 52 56 63 …6回目
●7回目は一度も交換をすることなく4番目が確定します。一度も交換しなかったということで、整列が完成したと判断させることにします。
●上の考え方をプログラムにします。やりかたはいろいろあります。一度も交換しなかったということで、整列が完成したと判断させるのは、プログラムができてから改めて考えることにします。
●前と同じです。数値を大きさの順に並べ替えて出力するプログラムを作ります。手始めに10個の数字を並び替えます。10個の数値はa(1)からa(10)までの配列にREAD文で代入します。
DATA 52,46,24,12,15,35,18,56,63,23 DIM a(10) FOR i=1 TO 10 READ a(i) NEXT i
●1回目は1番から10番まで、2回目は1番から9番までというように繰り返しました。途中でできあがらなければ1番から2番までの作業までやりますから、10〜2で9回の繰り返しになります。これを FOR i=1 TO 10-1 と書きましょう。わざわざ10-1にしたのは、10個以上データがある時にわかりやすくするためです。30個のデータでは FOR i=1 TO 30-1 となります。
●i は回数を表すとしました。i 回目は1番から 10-i+1 番までの作業となります。つまり 1 番と 2 番のデータを比較し、最後は 10-i 番と 10-i+1 番の比較になります。データの番号を j で表すと、FOR j=1 TO 10-i までにしておいて、j 番と、j+1 番を比較することにすれば 10-i+1 までやったことになります。
FOR i=1 TO 10-1
FOR j=1 TO 10-i
a(j)とa(j+1)を比較してa(j)が大きければ交換する。
NEXT j
NEXT i
●緑の部分は後で考えます。
FOR i=1 TO 10 PRINT a(i); NEXT i
●交換する部分です。 t という作業変数を使っています。
IF a(j)>a(j+1) THEN
LET t=a(j)
LET a(j)=a(j+1)
LET a(j+1)=t
END IF
●上記プログラムを完成させなさい。