Re: No Go To's Forever!

[tmoran@bix.com]

>Well that's a different algorithm. It tests J against D'Last
>twice as often as my formulation.
  I would hardly call that a different algorithm.  Rather a
different implementation of the same algorithm.  But if you
want to call it different...

>Actually most compilers won't fix this, so you will find that
>your version actually does run noticably slower that the
>original.
  Right.  For each call on Swap and restart of the scanning, plus
one additional time, J will be compared against D'last.  That's
going to be a relatively miniscule slowdown.  If the data is
in order, yours does N comparisons against J and mine does N+1.
If the data is sorted backwards, the worst case, yours does
N + N*(N-1)/2 + N*(N-1)*(N-2)/6 comparisons against J and mine
does an additional N*(N-1)/2+1  That's 66% more when N=2 (5 vs 3)
declining to 3% more when N=100 (171,701 vs 166,750) and so forth.
Hardly "twice as many".  And nobody who cared would use this
algorithm anyway.

>Please tackle the harder problem: Take the algorithm *I*
>presented, and remove the goto without changing the sequence
>of computations, and see if that result is clearer.

>  <<Do_It_Again>>
>     for J in 1 .. N - 1 loop
>        if D (J) < D (J + 1) then
>           Swap (D (J), D (J + 1));
>           goto Do_It_Again;
>        end if;
>     end loop;

This should be pretty close to the same run-time sequence of machine
operations, so I hope you'll accept it as "the same algorithm".
I don't find it as clear as the "changed algorithm" method.

      J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            J := D'first;             -- and start over
         end if;
      end loop;

>P.S. I don't find your changed algorithm clearer, precisely
>because of the peculiar duplicated check.
  Perhaps some comments would help?

   loop
     J := D'first;
     while J < D'last and then D(J) >= D(J+1) loop -- compare
       J := J+1;                                   -- continue if in order
     end loop;
     exit when J >= D'last;    -- If at end, we can't swap, but are done.
     Swap (D (J), D (J + 1));  -- Otherwise move item
   end loop;                   -- and start over

So gotos may be appropriate for Adventure games and other FSMs, but
a goto doesn't buy much for this sort algorithm.