Log In  

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!

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

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.

P#78903 2020-07-04 19:20 ( Edited 2020-07-05 22:51)

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
P#78924 2020-07-05 08:01 ( Edited 2020-07-05 08:01)
:: Felice

Hm, good point, testing it exclusively on 32-long lists was a bad plan. Lemme check.

P#78927 2020-07-05 08:13 ( Edited 2020-07-05 19:21)
:: Felice

@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?

P#78928 2020-07-05 08:18

I got 2 types of crashes:

  • with r>2 test: out of memory
  • without: nil exception

Bench cart attached:

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

P#78930 2020-07-05 13:39 ( Edited 2020-07-05 18:33)
:: Felice

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.

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.

P#78944 2020-07-05 18:56 ( Edited 2020-07-05 19:25)

??
your post doesn't have this l<r condition!
(and I confirm change that first line does the trick)

P#78947 2020-07-05 20:28 ( Edited 2020-07-05 21:13)
:: Felice

@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.

P#78957 2020-07-05 22:47
1

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

P#78970 2020-07-06 06:24

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2021-09-26 04:02:45 | 0.024s | Q:29