From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-1.9 required=3.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.5-pre1 Date: 1 Sep 93 17:02:45 GMT From: dst17!mab@ford-wdl1.arpa (Mark A Biggar) Subject: Re: Hoare's gripes about Ada (should be so what) Message-ID: <1993Sep1.170245.17746@wdl.loral.com> List-Id: In article smccoy@dr3w.ess.harris.com (Scott McCoy) writes: >In article <1993Sep1.030349.9524@seas.gwu.edu>, mfeldman@seas.gwu.edu >(Michael Feldman) writes: >|> I'll take a copy. An Ada version could turn up in an insanely great >|> data structures book. You'll get full credit, of course. >Heck, if you're taking contributions, why not include the SlowSort? >It has to be just about the *worst* sorting algorithm ever devised! >I use it as a orientation exercise in my Ada training courses. Kinda >fun to watch a 14 element sort take 10 minutes to finish! :-) I don't know what the algorithm for Slowsort is but the two worst sorting algorithms I know of are permutation-sort and 52-pickup-sort. Permutation-sort sometimes shows up in prolog programs by a naive translation of the declaritive definition of sorting directly into prolog: sort(List) :- permute(List),ordered(List). I.E. using a backtracking algorithm to produce succesive permutations of the original list and then checking if the new permutation is ordered. Even worse is 52-pickup sort, which is also easy to express in prolog: sort(List) :- random-shuffle(list),order(list). I.E. this is like sorting a deck of cards by throwing it up in the air, picking up all the cards (without looking at them) and then checking if they just happen to be sorted, if not repeat. You can't even express an big O bound for this alogorithm, only an expected number of iterations. -- Mark Biggar mab@wdl.loral.com