This book is one of the most general treatments of parameterized Quicksort available: http://wild-inter.net/publications/wild-2016.pdf
Pattern-defeating quicksort
71–79 of 79 posts
Re: Pattern-defeating quicksort
#72Re: Pattern-defeating quicksort
#73Earlier quoted context omitted.
Comparing sorting algo's often says more about your benchmark than the algo's themselves. Random and pathological are obvious, but often your dealing with something in between. Radix vs n log n is another issue. So, what where your benchmarks like?
That is true - the benchmarks mostly focus on random cases, although there are a few benchmarks with "mostly sorted" arrays (sorted arrays with sqrt(n) random swaps). If the input array consists of several concatenated ascending or descending sequences, then timsort is the best. After all, timsort was specifically designed to take advantage of that particular case. Pdqsort performs respectably, too, and if you have m…
There's lots of pathologies to watch out for...
Imagine sorting 10 million random ints, where 1% of them are random 64-bit values and 99% are in the range [0..9]. Might be extra fun in parallel.
Re: Pattern-defeating quicksort
#74Earlier quoted context omitted.
Just that it takes extra space and that's sometimes a constraint.
https://stackoverflow.com/questions/2571049/how-to-sort-in-p... In place merge sort exists. It's hard to write tho
Which decreases the space complexity but increases the time complexity.
Re: Pattern-defeating quicksort
#75Earlier quoted context omitted.
https://stackoverflow.com/questions/2571049/how-to-sort-in-p... In place merge sort exists. It's hard to write tho
Which decreases the space complexity but increases the time complexity.
No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity:
https://sites.google.com/site/algoxy/home/elementary-algorit...
Re: Pattern-defeating quicksort
#76Earlier quoted context omitted.
I'm sympathetic because it may not be clear: pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. Your thesis is wrong: > you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort Heapsort has a variable runtime. It will selec…
> pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. I understand how hybrid sorts work. I thought that would be clear enough. I guess when you're a stranger on the internet, people don't automatically trust you to know what you're talking about. I imagine this is even truer w…
I hear what you're saying, but it seems like this is potentially a problem only in cases where you are devoting significant resources to sorting. Like if sorting takes only 1% of your CPU time, worst-case input will only bump that to 4% - and that's only if every user starts hitting you with worst-case requests. Even if you spend more, it's a question of how much work can the malicious users cause you to do.
Re: Pattern-defeating quicksort
#77Earlier quoted context omitted.
Which decreases the space complexity but increases the time complexity.
No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity: https://sites.google.com/site/algoxy/home/elementary-algorit...
...but it increases run time. It's fine not to care on hidden constants while analyzing algorithms, but not while using them in real life
Re: Pattern-defeating quicksort
#78I always wondered if there would be a way to have quicksort run slower than O(n ln(n)). Due to that possibility, when I code up a sort routine, I use heap sort. It is guaranteed O(n ln(n)) worst case and achieves the Gleason bound for sorting by comparing keys which means that on average and worst case, on the number of key comparisons, it is impossible to do better than heap sort's O(n ln(n)) forever. For a stable s…
It's cool to play with a pack of cards and run sorting algorithms on them. To see the worst case of quicksort, use the first element as the pivot and give it an already sorted list. It will take quadratic time to give back the same list.
Right. So, for the first "pivot" value, people commonly use the median of three -- take three keys and use as the pivot the median of those three, that is, the middle value. Okay. But then the question remains: While in practice the median of three sounds better, maybe there is a goofy, pathological array of keys that still makes quicksort run in quadratic time. Indeed, maybe for any way of selecting the first pivot, there is an array that makes quicksort quadratic.
Rather than think about that, I noticed that heap sort meets the Gleason bound which means that heap sort's O(n ln)n)) performance both worst case and average case can never be beaten by a sort routine that depends on comparing keys two at a time.
Then, sure, can beat O(n ln(n)). How? Use radix sort -- that was how the old punched card sorting machines worked. So, for an array of length n and a key of length k, the thing always runs in O(nk) which for sufficiently large n is less than O(n ln(n)). In practice? Nope: I don't use radix sort!
Re: Pattern-defeating quicksort
#79it's interesting that .Net built-in quicksort is actually doing the same thing, with introsort behind the scenes.