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