Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!usc!apple!dan
From: dan@Apple.COM (Dan Allen)
Newsgroups: comp.sys.mac.hypercard
Subject: Re: Sorting Containers (HyperTalk Script)
Message-ID: <32831@apple.Apple.COM>
Date: 3 Jul 89 04:01:55 GMT
References: <15027.24ACEB9A@cmhgate.FIDONET.ORG>
Organization: Apple Computer Inc, Cupertino, CA
Lines: 25

In article <15027.24ACEB9A@cmhgate.FIDONET.ORG> Douglas.Welch@f823.n102.z1.FIDONET.ORG (Douglas Welch) writes:
>Thank you Dan,
> 
>This is exactly what I was looking for.  I haven't written a sort
>procedure in a long time and was not exactly looking forward to creating
>one from scratch.

Thanks for the thanks.  BTW, in my analysis of selection sorting I may
have left the wrong impression...

Selection sorting is on the average an O(n squared) algorithm for
comparisons, O(n ln n) for moves, and O(n squared) in the worst case.
The reason that sometimes selection sorting is quite zippy is that moves
are USUALLY a lot more expensive than comparisons, so on the average
selection sorting works out to be the best of the straight methods
(insertion, selection, exchange or bubblesort).  However, as someone has
already pointed out, the way my posted algorithm stands, the comparisons
are also quite expensive due to the way HyperTalk has to search for each
line linearly, not a performance boost to say the least.

If I get a few free minutes, maybe I'll try coding up QuickSort, which
will be a big win compared to selection sorting.

Dan Allen
Apple Computer