●バブルソートは、最小値を求めることをせずに、左から順に隣会った左右のデータを比べ、左側のデータが大きい時にはすぐに入れ換えを行なう方法です。バブルとは泡を意味していて、泡が浮くように小さな(プログラムの組み方で大きな)データが集まるように並べ換えが行なわれることからこう呼ばれている。
●次のような数字で実際にやってみます。
●まず、１番と２番を比べます。52と42で大きいのは52の方です。交換します。
52 46 24 12 15 35 18 56 63 23
●次に、２番と３番を比べます。52と24で大きいのは52の方です。交換します。
46 52 24 12 15 35 18 56 63 23
●次に、３番と４番を比べます。52と12で大きいのは52の方です。交換します。
46 24 52 12 15 35 18 56 63 23
●次に、４番と５番を比べます。52と15で大きいのは52の方です。交換します。
46 24 12 52 15 35 18 56 63 23
●次に、５番と６番を比べます。52と35で大きいのは52の方です。交換します。
46 24 12 15 52 35 18 56 63 23
●次に、６番と７番を比べます。52と18で大きいのは52の方です。交換します。
46 24 12 15 35 52 18 56 63 23
●次に、７番と８番を比べます。52と56で大きいのは56の方です。交換しません。
46 24 12 15 35 18 52 56 63 23
●次に、８番と９番を比べます。56と63で大きいのは63の方です。交換しません。
46 24 12 15 35 18 52 56 63 23
●次に、９番と10番を比べます。63と23で大きいのは63の方です。交換します。
46 24 12 15 35 18 52 56 63 23
●次に、９番と10番を比べます。63と23で大きいのは63の方です。交換します。
46 24 12 15 35 18 52 56 23 63
●これで最後まできました。これまでの操作で一番大きい63が最後に来ました。１０番はこれで確定です。さらにまだ完成していない１番から９番までについて作業をつづけます。
●２回目は１番から９番までについて作業します。
●１番と２番を比べます。46と24で大きいのは46の方です。交換します。
46 24 12 15 35 18 52 56 23 63
●２番と３番を比べます。46と12で大きいのは46の方です。交換します。
24 46 12 15 35 18 52 56 23 63
●３番と４番を比べます。46と15で大きいのは46の方です。交換します。
24 12 46 15 35 18 52 56 23 63
●同様に９番までやっていきます。説明は省略します。２回目の最後にはこのようになります。
24 12 15 35 18 46 52 23 56 63
●３回目は１番から８番までについて作業します。
●また１番と２番から比べますが、途中省略して最後だけ示します。
12 15 24 18 35 46 23 52 56 63
●４回目は１番から７番までについて作業します。
12 15 18 24 35 23 46 52 56 63
●これを繰り返すことで、１番から２番まで作業することになり、２番まで確定すれば、全部が並べ替えられたことになります。
12 15 18 24 23 35 46 52 56 63 …５回目
12 15 18 23 24 35 46 52 56 63 …６回目
●２番目の確定を待たずに途中で並び替えが完成してしまうことがあります。この場合も６回目で５番目が確定したらできあがっています。コンピュータが並び替えが完成したと判断して無駄な作業を省くことも考える必要がありそうです。
12 15 18 23 24 35 46 52 56 63 …６回目
●７回目は一度も交換をすることなく４番目が確定します。一度も交換しなかったということで、整列が完成したと判断させることにします。
●上の考え方をプログラムにします。やりかたはいろいろあります。一度も交換しなかったということで、整列が完成したと判断させるのは、プログラムができてから改めて考えることにします。
●前と同じです。数値を大きさの順に並べ替えて出力するプログラムを作ります。手始めに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
●１回目は１番から１０番まで、２回目は１番から９番までというように繰り返しました。途中でできあがらなければ１番から２番までの作業までやりますから、１０〜２で９回の繰り返しになります。これを FOR i=1 TO 10-1 と書きましょう。わざわざ10-1にしたのは、10個以上データがある時にわかりやすくするためです。30個のデータでは FOR i=1 TO 30-1 となります。
●i は回数を表すとしました。i 回目は１番から 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
●上記プログラムを完成させなさい。