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=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID 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: tmoran@bix.com Subject: Re: No Go To's Forever! Date: 2000/03/23 Message-ID: #1/1 X-Deja-AN: 601220286 References: <8bbsc6$aes$1@nnrp1.deja.com> X-Complaints-To: abuse@pacbell.net X-Trace: news.pacbell.net 953801191 206.170.2.159 (Thu, 23 Mar 2000 00:46:31 PST) Organization: SBC Internet Services NNTP-Posting-Date: Thu, 23 Mar 2000 00:46:31 PST Newsgroups: comp.lang.ada Date: 2000-03-23T00:00:00+00:00 List-Id: >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. > <> > 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.