szthlw
Last Updated: February 25, 2016
·
525
· aali

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

3 Responses
Add your response

5855

I though I had just invented recently. damn. Can I see it anywhere?

over 1 year ago ·
5856

I though I had just invented recently. damn. Can I see it anywhere?

over 1 year ago ·
6190

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) :-)

over 1 year ago ·