Quicksort: Choosing the pivot

Question

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? Something else?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Can someone help me grasp the concept of choosing a pivot and whether or not different scenarios call for different strategies.

Solution 1

Choosing a random pivot minimizes the chance that you will encounter worst-case O(n²) performance (always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data). Choosing the middle element would also be acceptable in the majority of cases.

Also, if you are implementing this yourself, there are versions of the algorithm that work in-place (i.e. without creating two new lists and then concatenating them).

Solution 2

It depends on your requirements. Choosing a pivot at random makes it harder to create a data set that generates O(N^2) performance. 'Median-of-three' (first, last, middle) is also a way of avoiding problems. Beware of relative performance of comparisons, though; if your comparisons are costly, then Mo3 does more comparisons than choosing (a single pivot value) at random. Database records can be costly to compare.

---

Update: Pulling comments into answer.

mdkess asserted:

'Median of 3' is NOT first last middle. Choose three random indexes, and take the middle value of this. The whole point is to make sure that your choice of pivots is not deterministic - if it is, worst case data can be quite easily generated.

To which I responded:

• Analysis Of Hoare's Find Algorithm With Median-Of-Three Partition (1997) by P Kirschenhofer, H Prodinger, C Martínez supports your contention (that 'median-of-three' is three random items).

• There's an article described at portal.acm.org that is about 'The Worst Case Permutation for Median-of-Three Quicksort' by Hannu Erkiö, published in The Computer Journal, Vol 27, No 3, 1984. [Update 2012-02-26: Got the text for the article. Section 2 'The Algorithm' begins: 'By using the median of the first, middle and last elements of A[L:R], efficient partitions into parts of fairly equal sizes can be achieved in most practical situations.' Thus, it is discussing the first-middle-last Mo3 approach.]

• Another short article that is interesting is by M. D. McIlroy, "A Killer Adversary for Quicksort", published in Software-Practice and Experience, Vol. 29(0), 1–4 (0 1999). It explains how to make almost any Quicksort behave quadratically.

• AT&T Bell Labs Tech Journal, Oct 1984 "Theory and Practice in the Construction of a Working Sort Routine" states "Hoare suggested partitioning around the median of several randomly selected lines. Sedgewick [...] recommended choosing the median of the first [...] last [...] and middle". This indicates that both techniques for 'median-of-three' are known in the literature. (Update 2014-11-23: The article appears to be available at IEEE Xplore or from Wiley — if you have membership or are prepared to pay a fee.)

• 'Engineering a Sort Function' by J L Bentley and M D McIlroy, published in Software Practice and Experience, Vol 23(11), November 1993, goes into an extensive discussion of the issues, and they chose an adaptive partitioning algorithm based in part on the size of the data set. There is a lot of discussion of trade-offs for various approaches.

• A Google search for 'median-of-three' works pretty well for further tracking.

Thanks for the information; I had only encountered the deterministic 'median-of-three' before.

Solution 3

Heh, I just taught this class.

There are several options.
Simple: Pick the first or last element of the range. (bad on partially sorted input) Better: Pick the item in the middle of the range. (better on partially sorted input)

However, picking any arbitrary element runs the risk of poorly partitioning the array of size n into two arrays of size 1 and n-1. If you do that often enough, your quicksort runs the risk of becoming O(n^2).

One improvement I've seen is pick median(first, last, mid); In the worst case, it can still go to O(n^2), but probabilistically, this is a rare case.

For most data, picking the first or last is sufficient. But, if you find that you're running into worst case scenarios often (partially sorted input), the first option would be to pick the central value( Which is a statistically good pivot for partially sorted data).

If you're still running into problems, then go the median route.

Solution 4

Never ever choose a fixed pivot - this can be attacked to exploit your algorithm's worst case O(n²) runtime, which is just asking for trouble. Quicksort's worst case runtime occurs when partitioning results in one array of 1 element, and one array of n-1 elements. Suppose you choose the first element as your partition. If someone feeds an array to your algorithm that is in decreasing order, your first pivot will be the biggest, so everything else in the array will move to the left of it. Then when you recurse, the first element will be the biggest again, so once more you put everything to the left of it, and so on.

A better technique is the median-of-3 method, where you pick three elements at random, and choose the middle. You know that the element that you choose won't be the the first or the last, but also, by the central limit theorem, the distribution of the middle element will be normal, which means that you will tend towards the middle (and hence, nlog(n) time).

If you absolutely want to guarantee O(nlog(n)) runtime for the algorithm, the columns-of-5 method for finding the median of an array runs in O(n) time, which means that the recurrence equation for quicksort in the worst case will be:

T(n) = O(n) (find the median) + O(n) (partition) + 2T(n/2) (recurse left and right)

By the Master Theorem, this is O(nlog(n)). However, the constant factor will be huge, and if worst case performance is your primary concern, use a merge sort instead, which is only a little bit slower than quicksort on average, and guarantees O(nlog(n)) time (and will be much faster than this lame median quicksort).

Explanation of the Median of Medians Algorithm

Solution 5

Don't try and get too clever and combine pivoting strategies. If you combined median of 3 with random pivot by picking the median of the first, last and a random index in the middle, then you'll still be vulnerable to many of the distributions which send median of 3 quadratic (so its actually worse than plain random pivot)

E.g a pipe organ distribution (1,2,3...N/2..3,2,1) first and last will both be 1 and the random index will be some number greater than 1, taking the median gives 1 (either first or last) and you get an extermely unbalanced partitioning.

View more solutions

Comments

[PeterAllenWebb]

I would second the notion that implementing a search yourself might not be worth the effort. Also, be careful how you're picking random numbers, since random number generators are kinda slow sometimes.

[mindvirus]

Median of 3 is NOT first last middle. Choose three random indexes, and take the middle value of this. The whole point is to make sure that your choice of pivots is not deterministic - if it is, worst case data can be quite easily generated.

[Sumit Kumar Saha]

I was reading abt introsort which combines good features of both quicksort and heapsort. The approach to select pivot using median of three might not always be favourable.

[Robert S. Barnes]

We did an experiment in our class, getting the k smallest elements from an array in sorted order. We generated random arrays then used either a min-heap, or randomized select and fixed pivot quicksort and counted the number of comparisons. On this "random" data, the second solution performed worse on average than the first. Switching to a randomized pivot solve the performance problem. So even for supposedly random data, fixed pivot performs significantly worse than randomized pivot.

[Kevin Chen]

The problem with choosing random indices is that random number generators are pretty expensive. While it does not increase the big-O cost of sorting, it will probably make things slower than if you had just picked the first, last, and middle elements. (In the real world, I bet nobody is making contrived situations to slow down your quick sort.)

[Chris Cudmore]

Finding the middle of 3 elements can be done in constant time . Any more, and we essentially have to sort the sub array. As n becomes large, we run right back into the sorting problem again.

[Aaron Franke]

Why would partitioning the array of size n into two arrays of size 1 and n-1 run the risk of becoming O(n^2)?

[Chris Cudmore]

Assume an Array of size N. Partition into sizes [1,N-1]. The next step is partitioning the right half into [1, N-2]. and so on, until we have N partitions of size 1. But, if we were to partition in half, we'd be doing 2 partitions of N/2 each step, leading to the Log(n) term of the complexity;

[Nathan]

@Jonathan Leffler's answer is better

[ncmathsadist]

cart in front of horse here.