From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.2 required=5.0 tests=BAYES_00,INVALID_MSGID,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,14f7200925acb579
X-Google-Attributes: gid103376,public
From: Jeff Carter <jrcarter@acm.org>
Subject: Re: No Go To's Forever!
Date: 2000/03/23
Message-ID: <38DA9505.F1AE2989@acm.org>#1/1
X-Deja-AN: 601507771
Content-Transfer-Encoding: 7bit
References: <8bbsc6$aes$1@nnrp1.deja.com>
 <HRkC4.1999$U95.38761@news.pacbell.net> <8bdbof$t19$1@nnrp1.deja.com>
X-Accept-Language: en
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: abuse@earthlink.net
X-Trace: newsread2.prod.itd.earthlink.net 953852694 63.10.53.48 (Thu,
 23 Mar 2000 15:04:54 PST)
Organization: EarthLink Inc. -- http://www.EarthLink.net
MIME-Version: 1.0
Reply-To: jrcarter@acm.org
NNTP-Posting-Date: Thu, 23 Mar 2000 15:04:54 PST
Newsgroups: comp.lang.ada
Date: 2000-03-23T00:00:00+00:00
List-Id: <comp.lang.ada>

Robert Dewar wrote:
> Let's once again look at my original:
> 
> >  <<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;


>    Continue := True;
>    Outer : while Continue loop
>       Continue := False;
>       Inner : for J in 1 .. N - 1 loop
>          if D (J) < D (J + 1) then
>             Swap (D (J), D (J + 1));
>             Continue := True;
>             exit Inner;
>          end if;
>       end loop Inner;
>    end loop Outer;

Personally, I find both of these a bit difficult to follow due to the
lack of documentation. Maybe I'm wrong, but I think a variation on the
goto-less version is easier to document because the 2 loop are explicit:

-- Sort D into descending order
Repeat_Until_Sorted : loop
   Sorted := True; -- Assume D is sorted

   Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
      if D (J) < D (J + 1) then -- Found an out-of-order pair if True
         Swap (D (J), D (J + 1) );
         Sorted := False; -- We have not determined that D is sorted

         exit Find_Out_Of_Order_Pair; -- Repeat to see if D now sorted
      end if;
   end loop Find_Out_Of_Order_Pair;

   exit Repeat_Until_Sorted when Sorted;
   -- Did not find out-of-order pair if Sorted
end loop Repeat_Until_Sorted;

Now I can see what the algorithm is doing: It scans D looking for an
out-of-order pair of adjacent values. If it doesn't find one, then D is
sorted. If it does find one, it swaps them and repeats the entire
process. This looks like elimination of tail-recursion:

Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
   if D (J) < D (J + 1) then
      Swap (D (J), D (J + 1) );
      Sort (D);

      exit Find_Out_Of_Order_Pair;
   end if;
end loop Find_Out_Of_Order_Pair;
-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail