[PD] [list-quicksort]

[Claude Heiland-Allen]

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