A while back I posted an implementation of an in-place dual-pivot quicksort, which is the default sort algorithm most standard libraries offer these days. I've since tweaked it a bit to save a few tokens, and today I wrote up a sample cart that does some primitive testing as an example of usage.
This includes both a general 221-token qsort(), which can accept a custom comparator function (defaults to a less-than comparator for ascending order), and a tweaked 199-token iqsort(), which inlines the comparisons as simple "<" operators, producing a smaller and faster sort in return for the sort order and index not being customizable.
See tab 0's header comment for more details.
(Side note: I realized while implementing comparators that you could sneak in shuffle functionality just by sorting with a random coin-flip comparator. Handy.)
Edit: WARNING! Do NOT grab the function from the "Code" flyout on the embedded cart below! There is a bug on the BBS right now that deletes a "<" comparison! Click the "Cart" button to download the .p8.png version!
Feel free to use it in any way you wish. I didn't invent the algorithm, and the implementation was inspired by looking at several other people's implementations (which in turn were inspired by other people's implementations, and so on). I'm not going to claim any original work here. I just did some grunt work tidying it up and applying ducktape where needed.
Please let me know ASAP if you find any bug. I think it's solid, but I know I'm not perfect.
It's crashing because you changed the outer condition from:
if l<r then
if l then
If I repair that, it seems to work fine. I also replaced qsort() with an iqsort() customized for your data type. It's more of a fair comparison to use the version that doesn't require a comparator, since your radix sort assumes ascending order.
It still doesn't do as well as your radix sort, but I think that's because the radix sort is able to assume simple numeric comparisons and optimize for that with what is essentially a multi-layered bucket sort. I offer qsort as the best general-purpose sort, but it's not the best specific-purpose sort.
Ah, I think I see what happened. Did you grab the code out of the "Code" flyout here on the BBS?
It looks like @zep has a bug with "<" characters in that feature. I see it's displaying without "l<r" here, but still has "l<r" when I download the cart as a png.
[Please log in to post a comment]