整列４(バブルの改良)

交換しなくなったら整列は終わっている

●バブルソートでコンピュータが並び替えが完成したと判断して無駄な作業を省くことを後回しにしました。これを考えてみます。

●次の部分で、たとえばi=5の時に１度も交換がなければ、i=6以降の作業は必要ありません。

FOR i=1 TO 10-1
   FOR j=1 TO 10-i
      a(j)とa(j+1)を比較してa(j)が大きければ交換する
   NEXT j
NEXT i

●そこで毎回、(iが変わるごとに)交換があったかを確認すればよいのです。

FOR i=1 TO 10-1
   回ごとに(i)交換がなかったことにする
   FOR j=1 TO 10-i
      a(j)とa(j+1)を比較してa(j)が大きければ交換し、
               交換があったことを記録する
   NEXT j
   交換がなかったら i についてのFOR〜NEXTは終わりにする
NEXT i

●具体的にはkoukanという変数をつくって、これが０のとき交換がない。１のとき交換があったということにします。

FOR i=1 TO 10-1
   LET  koukan=0
   FOR j=1 TO 10-i
      IF a(j)>a(j+1) THEN
         LET t=a(j) 
         LET a(j)=a(j+1)
         LET a(j+1)=t
         LET  koukan=1
      END IF
   NEXT j
   IF koukan=0 THEN EXIT FOR
NEXT i

●まず回が変わるごとに(iが変わるごとに)交換がなかったことにします。これをしないと、最初に交換があると最後まで交換があったことになります。

●交換した時にkoukan=1を実行します。これで１回でも交換がおきると記録されます。

●i回目の最後に交換あったかチェックします。なければ次の回は必要ないので、i のFOR〜NEXTを終了します。このBASICでは EXIT FOR という命令が使えます。もし、使えないときは、i=10 としてもいいでしょう。

●交換した時にkoukan=1、しないときにはkouka=0、 とその都度代入するのはだめです。つまり、

      IF a(j)>a(j+1) THEN
         LET t=a(j) 
         LET a(j)=a(j+1)
         LET a(j+1)=t
         LET  koukan=1
      ELSE
         LET  koukan=0
      END IF

これだとその回に交換があっても最後に交換しなければ０になってしまうからです。

ほんとに速くなるか

●さて、この改良で速くなるでしょうか。たしかに無駄なことをしないといえるのですが、その判断をするために、LET koukan=1 という作業をなんどもやっています。交換が必要なときにある LET 文が３つであったものが４つになるのですから、その分よけいな仕事をしていることになります。いったいどちらが速いのでしょうか。