Home  Back Topics CD Orders  INDEX 
Quicksort

Quicksort is a method of sorting data. The algorithm shown here is an example of recursion.

Make sure you follow how it works first...

Demo : Here are 16 records. Their keys are shown.

45 27 19 66 82 53 12 55 91 59 28 71 30 43 29 60

Take the 'middle' key and remember it as the 'pivot value'.
Set two pointer, LP (Left pointer) and RP (Right Pointer) at each end :

Pivot value = 55
45 27 19 66 82 53 12 55 91 59 28 71 30 43 29 60
LP                             RP

Step 1 : Move the LP to the right until a key which is greater than or equal to the pivot is found....

Pivot value = 55
45 27 19 66 82 53 12 55 91 59 28 71 30 43 29 60
      LP                       RP

Step 2 : Move the RP to the left until a key which is less than or equal to the pivot is found....

Pivot value = 55
45 27 19 66 82 53 12 55 91 59 28 71 30 43 29 60
      LP                     RP  

Step 3 : Swap these two records.

Pivot value = 55
45 27 19 29 82 53 12 55 91 59 28 71 30 43 66 60
      LP                     RP  

Repeat steps 1,2 and 3...

Pivot value = 55
45 27 19 29 43 53 12 55 91 59 28 71 30 82 66 60
        LP                 RP    

..and again...

Pivot value = 55
45 27 19 29 43 53 12 30 91 59 28 71 55 82 66 60
              LP         RP      

..and again...

Pivot value = 55
45 27 19 29 43 53 12 30 55 59 28 71 91 82 66 60
                LP       RP      

..and again...

Pivot value = 55
45 27 19 29 43 53 12 30 28 59 55 71 91 82 66 60
                LP   RP          

..and again...

Pivot value = 55
45 27 19 29 43 53 12 30 28 55 59 71 91 82 66 60
                  LP RP          

..until both pointers meet (at the pivot number)

Pivot value = 55
45 27 19 29 43 53 12 30 28 55 59 71 91 82 66 60
                  LP
RP		            

Now ...

  • the pivot number should be in the correct place (all the numbers to its left should be smaller and those on the right should be greater)
  • ..which means we now have two smaller lists to sort (coloured below)
  • ..and this means we are back to the problem we started with..so we can RECURSE...ie do the same as the above with each list...and so on...until each list is only one key long.
45 27 19 29 43 53 12 30 28 55 59 71 91 82 66 60

 

 

The Recursive algorithm for a Quicksort procedure would need to use two parameters..the start key and the end key of the sub-list to sort.

If we had a list of n keys to sort then...we would call the following procedure with the instruction

Quicksort(1,n);

Procedure Quicksort(first, last : integer);

var left, right, pivot : integer;

{Check if list has more than one key}
if last > first then

{set the pointers}
left = first;
right = last;
pivot = key[(left+right) div 2]

repeat

{move left pointer}
while key[left] <= pivot do
    left = left+1;

{move right pointer}
while key[right] >= pivot do
    right = right -1

swap key[left] and key[right]

until left = right;

{The Recursive bit}
Quicksort(first,left-1);
Quicksort(right+1, last);

endif

  

 

NB : There must always be a terminating condition in a recursive procedure.
Swapping is done with a third variable:

temp = key[left]
key[left] = key[right]
key[right] = temp
The procedure calls itself with different values as parameters.

 

 

Bubble sort is fast if the records are 'nearly sorted' - they may have been sorted before and had some new records added.

Quicksort is fast if the records are completely 'shuffled'.