Anne Dawson: Quicksort.htm  

Last updated: Saturday 4th August 2007, 6:53 PT

Please report any errors or omissions in this document:

anne.dawson@gmail.com

Quicksort

The Quicksort sorting algorithm was created in 1960 by British computer scientist Tony Hoare - currently Professor of Computer Science at Oxford University in England. Quicksort has a best case running time of O(NLogN), an average case running time of O(NLogN) and a worst case running time of O(N²).

This document explains how the Quicksort algorithm sorts by illustrating a sort on an array of ten integers into ascending order.

Quicksort works by dividing the array into two subarrays whereby all the values in one subarray are greater than all the values in the other subarray. This subdivision process is known as partitioning. The algorithm then recursively calls itself to partition each subarray into two more subarrays. This recursion continues until the array is completely sorted.

The Quicksort algorithm

Note: low and high refer to the limits of the array.

void Quicksort (int array[], int low, int high)

{

IF there are 0 or 1 element to sort

return;

IF there are two elements to sort THEN

if necessary, swap array[low] and array[high]

ELSE

{

rearrange (i.e. partition) the array so that

all values in array[low .. marker -1] are less than

all values in array[marker .. high]

Quicksort(array, low, marker - 1);

Quicksort(array, marker, high);

}

}

Quicksort performs best if it can partition the array into two subarrays of exactly half the size of the original. The following diagram shows the partitioning of an array of size 16 for the best case of Quicksort:

Quicksort performs best if it can partition the array into two subarrays of exactly half the size of the original. In this case, each recursive call reduces the size of the data to be sorted by a half. The figure above illustrates the best case scenario. In general, the best case number of recursive calls is O(N) and the best case array size per recursive call is O(LogN).

Performance

The run-time performance of the Quicksort algorithm depends upon the number of recursive function calls multiplied by the time spent executing each function call. Other than calling itself recursively, a single function call spends most of its time partitioning the data into subarrays. Partitioning the array depends on N, but the average size of the array (in the best case) is LogN. The Quicksort running time can thus be estimated as follows:

Quicksort time = number of function calls * time for one partitioning

= O(N) * O(LogN)

= O(N * LogN)

= O(N log N)

The Partitioning Algorithm

The partitioning method starts by selecting one element of the array as a pivot, the value against which all other elements of the array are compared. The choice of pivot can drastically affect the performance of the algorithm. In this algorithm, the pivot is the first element of the array, and the values are sorted into ascending order.

pivot = array[low];

lowSwap = low + 1;

highSwap = high;

do

{

Scan forward from lowSwap until encountering a value > pivot

and set lowSwap to index this value

Scan backwards from highSwap until encountering a value <= pivot

and set highSwap to index this value

IF lowSwap and highSwap did not cross THEN

swap array[lowSwap] and array[highSwap]

} while (lowSwap and highSwap have not crossed);

swap the pivot (array[low])

with the element where lowSwap and highSwap crossed

Consider the following example:

The array to be sorted has ten elements:

Animation of the above algorithm:

http://www.site.uottawa.ca/~stan/csi2514/applets/sort/sort.html

Click on the button,

then click on the down arrow besides the word Bubble Sort,

then select QuickSort, then click on the Go button.