The QuickSort Algorithm
QuickSort is a particularly effective and popular sorting algorithm. It
is a divide-and-conquer algorithm, working by splitting the data into two
parts and then sorting them recursively. Being recursive, it is often hard
to visualise what the algorithm is doing.
Here is the pseudocode algorithm for QuickSort:
quicksort(a, p, r)
if r>p then
j=partition(a, p, r)
quicksort(a, p, j-1)
quicksort(a, j+1, r)
partition(a, p, r)
do i=i+1 while (a[i]<pivot)
do j=j-1 while (a[j]>pivot)
if (i<j) exchange(a[i], a[j])
The Partition method receives a list or sublist,
and places the first element in its correct position within the list.
It also ensures that all elements to the left of this are smaller, and
all to the right are larger.
The best and average cases of Quicksort take O(nlogn) time.
Go to QuickSort demonstration
Help on using the Applet
Back to main Page