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 _______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
