Re: Hoare's gripes about Ada (should be so what)

[dst17!mab@ford-wdl1.arpa (Mark A Biggar)]

In article <CCoI96.DqH@jabba.ess.harris.com> 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