Partition @Quicksort
Those who love implementing our sweet-old quicksort, I would highly suggest partition method which takes place in MIT's Introduction to Algorithms. Don't we all love O(log n)?
Written by Ali
Related protips
3 Responses
I though I had just invented recently. damn. Can I see it anywhere?
I though I had just invented recently. damn. Can I see it anywhere?
Which one? There are several methods: deterministic with O(n²) worst-case, randomized with O(n log n) average, but still quadratic running time in the worst case.
But there is a way to actually achieve guaranteed Θ(n log n) time complexity if we choose a good pivot. The good pivot is one that splits an array in almost equal-sized chunks. So if we take a median as the pivot, we'd get O(n log n) worst-case performance (I won't prove it here, but it should be easy to see that we get type of a balanced tree with height of log n).
So the question is: how do we get the median of an array in linear time? It's not obvious, but there is a deterministic linear algorithm for it discovered by five Computer Science rockstars (Blum, Floyd, Pratt, Rivest, and Tarjan) called "Median of medians".
Unfortunately, despite of being asymptotically optimal this variant of quicksort has a bigger constant hidden in O, so on average it performs significantly worse than the randomized quicksort.
P.S. I love logarithms, but even more I love O(1) :-)
