Quicksort: divide and conquer

Quicksort is an algorithm based on the divide-and-conquer principle: a big problem is split into smaller ones, they are solved separately and the results are combined. In the first step a pivot is chosen from the array. The other elements are divided into three groups: those smaller than the pivot, equal to it and greater than it.

Then the smaller and greater groups are sorted by the same method, that is, recursively. A part with one element or none is already sorted, which is the base case of the recursion. A short Python version: def qs(a): return a if len(a) <= 1 else qs([x for x in a if x < a[0]]) + [x for x in a if x == a[0]] + qs([x for x in a if x > a[0]]).

Let the array be 5 2 8 1 5 with pivot 5. Smaller: 2 1, equal: 5 5, greater: 8. Sorting 2 1 gives 1 2, so the result is 1 2 5 5 8. If the pivot splits the array roughly in half, the depth is about log₂ n and the total work is proportional to n · log₂ n; for 1,000,000 elements that is about 20 million operations instead of the 500 billion of bubble sort.

The worst case of quicksort is when the pivot is the smallest or the largest element every time: then the time approaches n². To avoid this, the pivot is taken from the middle or at random. In practice Python’s ready-made sorted() is used for sorting, while quicksort is the best example for learning the divide-and-conquer idea.

Key takeaways

Quicksort splits the array around a pivot into smaller, equal and greater elements.
The smaller and greater parts are sorted recursively by the same method.
On average the time is proportional to n · log₂ n, much faster than bubble sort.
In the worst case (the pivot is an extreme element every time) the time approaches n².
In practice the ready-made sorted() is used.

Practice tasks

Sort the array 4 9 1 7 4 3 by hand with quicksort: at each step write the pivot and the groups of smaller, equal and greater elements (the pivot is the first element of the array).
Put the qs function above into a file and test it on a list of 10 random numbers. Compare the result with the result of sorted().
Modify the function so that it sorts in descending order. Work out which conditions must be swapped and test the program.

Review questions

Test yourself: think first, then reveal the answer.

1What is the pivot needed for in quicksort?Show answer

Elements are divided into smaller, equal and greater ones relative to it, so the pivot ends up in its place.

2When does quicksort work slowest?Show answer

When the pivot is the smallest or the largest element every time: the time approaches n².