Using median selection in quicksort?

Question

I have a slight question about Quicksort. In the case where the minimun or maximum value of the array is selected, the pivot value the partition is very inefficient as the array size decreases by 1 one only.

However if I add code of selecting the median of that array, I think then Ii will be more efficient. Since partition algorithm is already O(N), it will give an O(N log N) algorithm.

Can this be done?

can what be done? why not try and implement your changes and find out? — Colin D
@Batman, I think that sch is hinting that in order to find the median, you have to sort the array. — Omri Barel
@OmriBarel: You don't need to sort the array to find the median. There are O(n) solutions. Having said that, real-world quicksort implementations typically use a media-of-three or median-of-nine algorithm to select a pivot value. — Blastfurnace
@Blastfurnace is right. Also, it is not worth computing the median of the entire array because it would increase the running time on average. The constant factor on quicksort is smaller than that of selection algorithms. — fgp

templatetypedef templatetypedef · Accepted Answer · 2012-08-27T19:34:48

You absolutely can use a linear-time median selection algorithm to compute the pivot in quicksort. This gives you a worst-case O(n log n) sorting algorithm.

However, the constant factor on linear-time selection tends to be so high that the resulting algorithm will, in practice, be much, much slower than a quicksort that just randomly chooses the pivot on each iteration. Therefore, it's not common to see such an implementation.

A completely different approach to avoiding the O(n²) worst-case is to use an approach like the one in introsort. This algorithm monitors the recursive depth of the quicksort. If it appears that the algorithm is starting to degenerate, it switches to a different sorting algorithm (usually, heapsort) with a guaranteed worst-case O(n log n). This makes the overall algorithm O(n log n) without noticeably decreasing performance.

Hope this helps!

Using median selection in quicksort?

1 Answers