Fwd: Re: Quicksort Implementation v1.0.2
Fwd: Re: Quicksort Implementation v1.0.2
- Subject: Fwd: Re: Quicksort Implementation v1.0.2
- From: Nigel Garvey <email@hidden>
- Date: Sat, 2 Aug 2003 10:44:27 +0100
Emmanuel's asked me to forward this contribution to the thread. He's on
holiday and the AS-Users server is apparently bouncing posts from his
hotel.
I myself am just about to catch up on a load of stuff I received from
Rick late last night....
NG
---------------- Begin Forwarded Message ----------------
At 6:31 PM -0400 01/08/03, Rick Bargerhuff alias cougar wrote:
>
Hello folks,
>
>
My Quicksort Implementation is at version 1.0.2. Nigel and I have been
making revisions to the source and
>
right now it is extremely quick. Takes about 1 second for every 1000 items.
Thanks and congratulations to Rick and Nigel for providing a carefully
optimized list-of-lists sorting routine.
However, quicksort is recursive and people who use it live dangerously.
For instance, you would think that quicksort can safely sort a list of
400 items, wouldn't you? Now try to sort that list (I'm not considering
lists of lists here, just ordinary lists of integers):
---------------------
set x to {}
repeat with i from 1 to 200
set end of x to 2 * i
set end of x to 401 - 2 * i
end repeat
---------------------
OMM quicksort returns a stack overflow error on that list.
This is why, for safety, we use a heapsort algorithm instead. I recall
the following facts:
1. heapsort is slower than quicksort on the average (whence the "quick"
denomination)
2. heapsort's speed is less dependent than quicksort's on the order of
the original list
3. heapsort won't trigger any stack overflow, unlike quicksort (like the
example above demonstrates)
4. heapsort can be tuned so as to return a list with only the k larger
items sorted in the k first positions (e.g. {1000,999,998,144,938,34,
etc.} for k=3), and then it works faster of course
5. Smile offers public implementations of both, you can use them and you
can use their codes ("sort" and "heapsort").
Emmanuel
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.