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
def quicksort(myList, start, end): if start < end: # partition the list pivot = partition(myList, start, end) # sort both halves quicksort(myList, start, pivot-1) quicksort(myList, pivot+1, end) return myList
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
def partition(myList, start, end): pivot = myList[start] left = start+1 right = end done = False while not done: while left <= right and myList[left] <= pivot: left = left + 1 while myList[right] >= pivot and right >=left: right = right -1 if right < left: done= True else: # swap places temp=myList[left] myList[left]=myList[right] myList[right]=temp # swap start with myList[right] temp=myList[start] myList[start]=myList[right] myList[right]=temp return right
- 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.