[PD] [list-quicksort]

[Matt Barber]

Hello,

Attached is a [list-quicksort] abstraction, which sorts lists of
numbers using (you guessed it!) a quicksort algorithm... it should
function as a drop-in replacement for the recent [list-*sort]
abstractions, and it should be quite a bit faster than [list-sort],
and faster than [list-shellsort] for lists of maybe 50 or more.  It
will not perform as well as [list-shellsort] for lists that have a ton
of duplicates, and it uses more memory than the shellsort.

I believe there are faster sorting algorithms which begin with
quicksort and then move to another kind of sort for short partitions
or if the partitioning gets too deep, but I wanted to do a pure
quicksort for simplicity.

Anything significantly faster would probably need an external, but
like I said before I love this kind of thing just for the constrained
problem solving, and for the pedagogical value for anyone who uses
list-abs.  I don't think we "need" a heapsort or anything else, but
I'd be happy to put one together in a couple of weeks.

There were a few persistent bugs in this one that I think I've ironed
out, but I'd like to have one or two people try to break it.  =o)

Thanks,

Matt
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: list-quicksort.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20081206/d18340de/attachment.asc>