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.
Dropped into Virtua Racing and got nil exception.
Are you sure this is working for non-even tables?
You also should add an early exit statement:
— empty/single element array if(r<2) return |
Hm, good point, testing it exclusively on 32-long lists was a bad plan. Lemme check.
I tried passing in lists of random length and didn't get any nil exceptions. Can you supply me with a minimal repro case? Or at least something representative of the data it's failing on?
I got 2 types of crashes:
- with r>2 test: out of memory
- without: nil exception
Bench cart attached:
It's crashing because you changed the outer condition from:
if l<r then |
to
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.
??
your post doesn't have this l<r condition!
(and I confirm change that first line does the trick)
[Please log in to post a comment]
