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!

Dual-pivot qsort() test/demo

Cart File | Forum Post |

	More cartridges by Felice

More Cartridges [View All]

 

Dual-pivot qsort() test/demo

by Felice

Cart #putikutuke-0 | 2020-07-04 | Code ▽ | Embed ▽ | No License

6

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.

@freds72

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:

kifuworeke

by freds72

Cart #kifuworeke-0 | 2020-07-05 | Code ▽ | Embed ▽ | No License

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.

yiwanasaba

by Felice

Cart #yiwanasaba-0 | 2020-07-05 | Code ▽ | Embed ▽ | No License

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)

@freds72

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.

yes (cause I don’t have 2.1 yet). That’s a very nasty bug!!