MOO-cows Mailing List Archive
RE: sort functions
Date: Wed, 11 Sep 1996 21:47:30 PDT
From: Roger Crew <firstname.lastname@example.org>
Encoding: 49 TEXT
$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) should be
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:email@example.com]
>Sent: Wednesday, September 11, 1996 6:11 AM
>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
Subject Index |