Last Updated: February 25, 2016
·
657
· 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)?

81.64K
10

59.87K
0

### Swift: Create an array of numbers 1 to 100 and divide into odds and evens using partition()

21.8K
0

#### 3 Responses

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

over 1 year ago ·

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

over 1 year ago ·

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 ·

#### Have a fresh tip? Share with Coderwall community!

Best #Algorithms Authors
nevir
81.21K
namuol
59.8K
synth
3.805K
Awesome Job