Quicksort improvement

DSP, Plugin and Host development discussion.
RELATED
PRODUCTS

Post

I'm not really good at promoting what I do. But I've developed this deep modification of the quicksort algorithm that has vast improvements over the classical quicksort. After about four years of work of trying almost every possible sorting variation I could find and developing numerous other methods of sorting in the way, I released this back in 2015. It's way faster than the regular C/C++ library qsort and std:sort.

It's been sitting there doing almost nothing, so I thought may be someone here could use it.

Full paper is here: https://arxiv.org/ftp/arxiv/papers/1505/1505.00558.pdf

Fully working C++ compiler optimized version can be found here: http://solostuff.net/tsqsort/Triple_Sta ... C1.0.5.zip

Code is absolutely FREE for any use. If you use it somewhere, would be nice to tell me. Just for my self satisfaction. But ofcourse you don't have to.

More can be found here: http://solostuff.net/tsqsort/
www.solostuff.net
Advice is heavy. So don’t send it like a mountain.

Post

Cool project, not sure I have any use for it. Not much sorting is done in my plugins... not quite what I would even sort in a plugin other than perhaps presets but the numbers are too small to make a noticeable difference between algorithms.
I suggest you post this in another forum as well. I think most plugin/DSP applications are not very sort-heavy.
David Guda gudaaudio.com

Post

Nice work. Those header files look complex.

Post

davidguda wrote: Wed Feb 20, 2019 11:41 am Cool project, not sure I have any use for it. Not much sorting is done in my plugins... not quite what I would even sort in a plugin other than perhaps presets but the numbers are too small to make a noticeable difference between algorithms.
I suggest you post this in another forum as well. I think most plugin/DSP applications are not very sort-heavy.
I suppose yeah, not much sorting in audio :). I've posted in Microsoft forum before, there were some few discussions there. May be I should try somewhere else.
quikquak wrote: Wed Feb 20, 2019 12:42 pm Nice work. Those header files look complex.
It is ugly complex. There is another version without the memory/cpu/compiler dependent optimization. This is much simpler to grasp and more portable to other languages, exactly the same algorithm though. Here http://solostuff.net/tsqsort/Triple_Sta ... d1.0.4.zip
www.solostuff.net
Advice is heavy. So don’t send it like a mountain.

Post

Thanks. The only time I've used a 'sort' would be to Z-order transparent polygons in an ancient renderer. And I suppose non time critical things like file name sorting or preset name sorting. I can't think of where that would be interested, sorry.

Post

S0lo wrote: Wed Feb 20, 2019 10:39 am I'm not really good at promoting what I do.
Apparently not. Anybody who can take a foundational algorithm that's been studied and analyzed six ways from Sunday and improve its performance by a sizeable margin ought to be working for Oracle or IBM and pulling in a sh*t-ton of money! :)

Post

I also can't see an application of sorting in DSP. The data structures we user are just too... structured to need sorting. If you sped it up 100x using magic, I guess one could develop a field of math that uses sorting to solve unrelated problems, but I'm assuming you're in the 1-2x range.
VCV Rack, the Eurorack simulator

Post

Useful or not, this looks like a pretty insightful modification to the quicksort algorithm:)
Would I use it? Probably not, but it was interesting to see that even quicksort could be improved.
~stratum~

Post

You MUST get someone specialized enough to test your proposal and confirm the speed improvement.
"I used to think I was indecisive, but now I'm not too sure."
Checkout my blog: VST Plugins Free Download.

Post

While I have a few places where I need to sort stuff (eg. related to rendering), I've pretty much got used to just using in-place heapsort (on the CPU anyway) for it's predictable performance. I wouldn't mind a faster algorithm (eg. smoothsort might theoretically be worthwhile) for some of that stuff, but I'm not really going to bother with anything that doesn't have a deterministic O(NlogN) upper bound.

edit: also much of what I do is stuff where cache (instruction and data) matters a lot, so increasing the complexity of a sorting algorithm must give a predictable improvement in running time that offsets the slowdowns it causes elsewhere; as it turns out, heap-sort implementation is not just predictable, it's also small

Post

Apparently since C++11, std::sort() is required to have O(NlogN) worst case as well.

Post

mystran wrote: Thu Feb 21, 2019 4:49 am While I have a few places where I need to sort stuff (eg. related to rendering), I've pretty much got used to just using in-place heapsort (on the CPU anyway) for it's predictable performance. I wouldn't mind a faster algorithm (eg. smoothsort might theoretically be worthwhile) for some of that stuff, but I'm not really going to bother with anything that doesn't have a deterministic O(NlogN) upper bound.

edit: also much of what I do is stuff where cache (instruction and data) matters a lot, so increasing the complexity of a sorting algorithm must give a predictable improvement in running time that offsets the slowdowns it causes elsewhere; as it turns out, heap-sort implementation is not just predictable, it's also small
Brief research usually says that Quicksort worst case is O(N^2). What they don't say is how probable that worst case is. Check Section V part B in my paper above where I calculate a an estimate of that probability.

For a well made quicksort (Not the text book one). Chances are really really slim that you would hit a worst case once in a life time. Let's just say that your more likely to guess a 30 character complex password on first try. Or stumble on gold thrown in the street while on your way home today (albeit thats a best case for you :)). Also check Section V part C where I describe a method for worst case mitigation

The thing with Heapsort is that it just doesn't cut it on the average when compared to quicksort. Yeah if your doing small sorts once in a while, I won't bother either. But repeated sortings thousands of times for large data is going to make a difference.

There is something called Introsort. It uses quicksort by default but automatically fallsback to heapsort if it hits a worst case. This is actually what the std:sort() function uses (Well at least in VC++). This is a rather "play it safe" solution. Though Java still uses quicksort (dual pivot) as far as I recall. Oracle and Microsoft wouldn't stick with quicksort if it didn't have an edge. Why would they.

For an airplane or a space shuttle. Yeah, may be I would think twice before I use just plane quicksort. That is an odd critical case, but then run time in those cases is also critical. So bare bones heapsort may not be good either.
www.solostuff.net
Advice is heavy. So don’t send it like a mountain.

Post

The worst case is when the array is already in order, and that's actually a high probability.
https://www.geeksforgeeks.org/when-does ... ort-occur/

Apparently there are ways to avoid it, but most people would just call whatever the standard library has instead of working on such things. I guess that's why they rarely are improved nowadays:)
~stratum~

Post

stratum wrote: Thu Feb 21, 2019 8:27 am The worst case is when the array is already in order, and that's actually a high probability.
https://www.geeksforgeeks.org/when-does ... ort-occur/
Yup, thats when you use a naive text book quicksort. Example, picking pivots out from the first element. No one does that any more if they know what they are doing. But I understand that developers who are not into this field and just want to use a ready made quicksort could fall into that.

In the paper I describe how these things has been already avoided like 20 years back. These are the first steps into a usable quicksort.
www.solostuff.net
Advice is heavy. So don’t send it like a mountain.

Post

Yeah, I was just reading about that https://www.geeksforgeeks.org/can-quick ... omplexity/
Apparently my knowledge of quicksort is older than 20 years:) Indeed that was actually the last time I had looked into it.
~stratum~

Post Reply

Return to “DSP and Plugin Development”