Quicksort is what is known as a divide and conquer algorithm. What it attempts to do is to split the problem in to smaller sections, known as partitions and then attempt to sort these smaller partitions.

Note - this is split over a number of pages. Check the related box!

The basic outline of the algorithm is

  • the first element of the list is chosen to be the pivot
  • Every element of the list is compared to the pivot. Anything less than the pivot is placed to the left, anything greater is placed to the right.
  • The pivot is then said to be sorted and will not be compared again.
  • Everything to the left and right of the pivot will become a new partition and quicksort will run again on each of these new partitions.

The best way to describe how quicksort works is through an example. Consider the list of numbers below.

Step 1 - Choose a pivot

The first element of the list will become the pivot.

Step 2 - Order all elements of the partition

You must pass over all of the numbers in the list. Any number less than the pivot should be placed on the left partition while all numbers greater of equal to the pivot should be placed on the right.

64 is greater than the pivot so should be placed to the right hand side.

Next we compare 32 to the pivot. It is less so it is placed on the left partition