MOO-cows Mailing List Archive
[Prev][Next][Index][Thread]

RE: sort functions

$list_utils:sort() does an insertion sort, a quadratic algorithm, but
since the insertions are done using the 2-tick listinsert() and
interpretation overhead in MOO is relatively large, you have to get to
fairly big lists (length in the hundreds, as I recall) before you start
losing w.r.t. the more funky methods.

$list_utils:sort_alist() does a merge sort which is tick intensive, but
guaranteed O(nlogn) --- unlike quicksort which is only O(nlogn) on
average.  Adapting :sort_alist() to sort lists (i.e., sort key is
element itself) instead of alists (sort key is element[1]) should be
straightforward.

Another route to an O(nlogn) sort routine is to code up the
insertion-sort using $biglist (list insertion on a $biglist is O(logn)
time --- really what you'd be doing is implementing a tree sort, even
though it'll look like an insertion sort).  This would probably be about
as tick-intensive as :sort_alist.

>----------
>From: 	Colin McCormick[SMTP:colin@tripod.tripod.com]
>Sent: 	Wednesday, September 11, 1996 6:11 AM
>To: 	moo-cows@parc.xerox.com
>Subject: 	sort functions
>
>
>Let's see, I'll try this one more time ...
>
>Hello folks --
>
>I'm interested in doing some fast list sorting, using the Quicksort
>algorithm.  $list_utils:sort(), as far as I can tell, is a straight linear
>sort and so doesn't fit my needs. 
>
>Does anyone have MOO code for a faster sort routine?  Has anyone
>implemented it as a server builtin?  This latter option is the more
>tempting to me, as it'd be easy to take advantage of C's qsort() library
>function. 
>
>Thanks,
>Colin
>
>
>Colin McCormick
>Tripod, Inc.
>http://www.tripod.com
>
>
>
>
Home | Subject Index | Thread Index