[Prev][Next][Index][Thread]

# RE: sort functions

- Date: Wed, 11 Sep 1996 21:47:30 PDT
- From:
- 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[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
    >
    >
    >
    >

- Prev: sort functions
- Next: Traceback from @edit
- Index: MOO-cows
- Thread: MOO-cows

Home | Subject Index | Thread Index