[PD] [list-quicksort]

[Matt Barber]

Right, this has been on my mind a lot.  It would take me a while to
figure this out, as I'm no Big-O expert.  I have sometimes put in a
few extra steps to make the code easier to read or to make it lie
better spatially in the patch, but usually this is only something like
an extra float store and I don't think that adds to the overall
complexity.  You're right, though -- filtering the non-floats is the
costliest part of the operation (lists of 20000 members or so take
about 3 times as long).  But seriously who's gonna be using
20000-element lists in Pd practice?

If there were a vanilla equivalent of [iter], this would be a lot
better.  Attached is a [list-shellsort] and [list-quicksort] which do
the filtering process as part of writing the table -- this cuts down
time -- but unfortunately it removes the instructive use of
[list-filter].

Matt



On Sat, Dec 6, 2008 at 12:07 PM, Claude Heiland-Allen
<claudiusmaximus at goto10.org> wrote:
> Have you analysed (or measured) the asymptotic complexities of the
> implementations?
>
> Note they may be different from the "standard" complexities [1] because of
> the non-optimal primitives [2] that Pd provides.
>
>
> Claude
>
> [1]
> http://en.wikipedia.org/wiki/Sorting_algorithms#List_of_sorting_algorithms
>
> [2]
> eg: [list split 1] loop to implement [list-drip] would copy O(n^2) atoms
>
>
> Matt Barber wrote:
>>
>> 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-shellsort.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20081206/b5155755/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: list-quicksort.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20081206/b5155755/attachment.asc>