MOOcows Mailing List Archive
[Prev][Next][Index][Thread]
RE: sort functions

Date: Wed, 11 Sep 1996 21:47:30 PDT

From: Roger Crew <rfc@microsoft.com>

Encoding: 49 TEXT
$list_utils:sort() does an insertion sort, a quadratic algorithm, but
since the insertions are done using the 2tick 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
insertionsort 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 tickintensive as :sort_alist.
>
>From: Colin McCormick[SMTP:colin@tripod.tripod.com]
>Sent: Wednesday, September 11, 1996 6:11 AM
>To: moocows@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