Pattern-defeating quicksort
github.com
Pattern-defeating quicksort
1–10 of 79 posts
Re: Pattern-defeating quicksort
#2Anyone knows how this compares to Timsort in practice?
A quick google turns out nothing
Re: Pattern-defeating quicksort
#3I would love to see the benchmark results against Timsort, the Python sorting algorithm that also implements a bunch of pragmatic heuristics for pattern sorting. Timsort has a slight advantage over pdqsort in that Timsort is stable, whereas pdqsort is not.
I see that timsort.h is in the benchmark directory, so it seems odd to me that the README doesn't mention the benchmark results.
Re: Pattern-defeating quicksort
#4Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
Re: Pattern-defeating quicksort
#5Is there a analysis of its complexity ? The algorithm looks very nice !
Re: Pattern-defeating quicksort
#6Is there a analysis of its complexity ? The algorithm looks very nice !
Hey, author of pdqsort here, the draft paper contains complexity proofs of the O(n log n) worst case and O(nk) best case with k distinct keys: https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
Re: Pattern-defeating quicksort
#7Where is a high level description of the algorithm? How is it different from quick sort, it seems quite similar based on a quick observation of the code.
The readme file actually contains a fairly thorough description of how it differs from quicksort. Start with the section titled "the best case".
Re: Pattern-defeating quicksort
#8I would love to see the benchmark results against Timsort, the Python sorting algorithm that also implements a bunch of pragmatic heuristics for pattern sorting. Timsort has a slight advantage over pdqsort in that Timsort is stable, whereas pdqsort is not. I see that timsort.h is in the benchmark directory, so it seems odd to me that the README doesn't mention the benchmark results.
There are multiple reasons I don't include Timsort in my README benchmark graph:
1. There is no authoritative implementation of Timsort in C++. In the bench directory I included https://github.com/gfx/cpp-TimSort, but I don't know the quality of that implementation.
2. pdqsort intends to be the algorithm of choice of a system unstable sort. In other words, a direct replacement for introsort for std::sort. So std::sort is my main comparison vehicle, and anything else is more or less a distraction. The only reason I included std::stable_sort in the benchmark is to show that unstable sorting is an advantage for speed for those unaware.
But, since you're curious, here's the benchmark result with Timsort included on my machine: http://i.imgur.com/tSdS3Y0.png
This is for sorting integers however, I expect Timsort to become substantially better as the cost of a comparison increases.
Re: Pattern-defeating quicksort
#9Rust's stable sort is based on timsort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...) and unstable sort is based on pattern-defeating quicksort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted sequences.'
Re: Pattern-defeating quicksort
#10[Post-edit] I made several edits to the post below. First, to make an argument. Second, to add paragraphs. [/Post-edit]
Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort.
Long version:
Here's my reasoning for the above:
You're either working with lists that are reasonably likely to trigger the worst case of randomised quicksort, or you're not working with such lists. By likely, I mean the probability is not extremely small.
Consider the case when the worst case is very unlikely: you're so unlikely to have a worst case that you're gaining almost nothing for accounting for it except extra complexity. So you might as well only use quicksort with optimisations that are likely to actually help.
Next is the case that a worst case might actually happen. Again, this is not by chance; it has to be because someone can predict your "random" pivot and screw with your algorithm; in that case, I propose just using heapsort. Why? This might be long, so I apologise. It's because usually when you design something, you design it to a high tolerance; a high tolerance in this case ought to be the worst case of your sorting algorithm. In which case, when designing and testing your system, you'll have to do extra work to tease out the worst case. To avoid doing that, you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort.