Quicksort is a very efficient sorting algorithm invented by C.A.R. Hoare. It has two phases:
- the partition phase
- the sort phase
Most of the work is done in the partition phase - it works out where to divide the work. The sort phase simply sorts the two smaller problems that are generated in the partition phase.
This makes Quicksort a good example of the divide and conquer strategy for solving problems. This is similar in principle to the binary search. In the quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions, ie we divide the problem into two smaller ones and conquer by solving the smaller ones.
The conquer part of the quicksort routine looks like this:
1 2 3 4 5 6 7 8
The divide part of the algorithm looks like this in Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
- Download an implemented version of the quicksort program and test that it works.
- Extend this program by adding a counter to count the number of comparisons.
- Compare your count with the insertion sort (next page) to see which is the most efficient sort.