Quicksort

The general strategy behind a quicksort procedure is that you divide a list into two partitions. One partition contains all of the values less than a value chosen as the pivot and the other contains all the values greater than the pivot. You then recursively split each partition (if it contains more than one item) using the same method until the original list is completely sorted. This is ideally suited to a recursive procedure. (See our tutorial for an introduction to recursion).

Different implementations of quicksort choose the pivot as:
  1. a value with a position in the middle of the list;
  2. the first item in the list;
  3. the median value in the list;
  4. an item chosen at random.

The Free Pascal code behind Lazarus uses a quicksort to sort items in a StringList object. It makes a random choice of pivot. Our first demonstration, based on a Czech wikipedia page, uses the first option.

The essential code for sorting the integers in the Ints array, stripped of comments and output, is neat:

procedure Quicksort(Left, Right: integer);
var
  ptrLeft, ptrRight, Pivot, Temp: integer;
begin
  ptrLeft := Left;
  ptrRight := Right;
  Pivot := Ints[(Left + Right) div 2];
  repeat
    while (ptrLeft < Right) and (Ints[ptrLeft] < Pivot) do
      inc(ptrLeft);
    while (ptrRight > Left) and (Ints[ptrRight] > Pivot) do
      dec(ptrRight);
    if ptrLeft <= ptrRight then  
      begin
        if ptrLeft < ptrRight then
          begin
            Temp := Ints[ptrLeft];
            Ints[ptrLeft] := Ints[ptrRight];
            Ints[ptrRight] := Temp;
            DisplayArray;
          end;
        inc(ptrLeft);
        dec(ptrRight);
     end;
  until ptrLeft > ptrRight; 
  if ptrRight > Left then
    Quicksort(Left, ptrRight);
  if ptrLeft < Right then
    Quicksort(ptrLeft, Right);
end;      
In the first two while loops:
  • The left pointer starts at the extreme left of the list and moves right if necessary until it reaches the pivot or finds a value that should be placed after the pivot.
  • Similarly, the right pointer starts at the extreme right and moves left if necessary until it reaches the pivot or a value that should be placed before the pivot.
After the pointers have stopped moving:
  • If the pointers have crossed the current partitioning is complete and the pointers then usually become arguments to further calls of the Quicksort procedure. Otherwise ...
  • If the pointers are different the values they point to are swapped. After the swap, both pointers need to be moved one place because the values to which they currently point are now in their correct partitions.
  • If the pointers meet and stop in the same position, this must be at the pivot. All values to the left are less than the pivot and all values to the right are greater. The pivot value should not be included in either partition so each pointer moves one place and usually becomes an argument to a further call of the Quicksort procedure.
Partitioning is always complete when the pointers have crossed each other.
  • The left partition comprises indexes from the left of the current list up to the final position of the right pointer and the right partition comprises indexes from the final position of the left pointer to the end of the current list.

In the first stages of this process swaps of data items are likely to move the items relatively large distances. (Compare this with bubble sort, where adjacent items are swapped). As a consequence, sorting is quick (hence the name) and, as the sorting time for size N increases as N x log N, quicksort works efficiently for large lists.

In our first version of quicksort, the pivot may move and may end up in either partition or neither depending on the initial order of the list. Proqram QuicksortDemo1a uses the crt unit (available in Lazarus but not in Delphi) to display coloured output of the many stages of the sort. Examine the annotated screenshots below to learn about the ordering of a 10-item list. We demonstrate all of the steps for completeness. Only study as many steps as you need to understand quicksort. We now provide a Smart Pascal web version of the demonstration with the output inside a ScrollBox.

Quicksort Screenshot 1

Quicksort Screenshot 1


The value 10 swaps with 4 because already 10 is greater than 8 and 4 is less than 8.
After the swap, both pointers move.
The green left pointer does not point to any values needing a swap and it makes its way as far as the pivot.
The red right pointer points at 1, which is less than 8, so the swap proceeds. After the swap, both pointers move.        
      

Quicksort Screenshot 2

Quicksort Screenshot 2


The left pointer can now move since the pivot has shifted. It moves as far as the value 9 where it stops, because 9 is greater than 8.
The right pointer moves left because it is 'looking for' values less than  8.  

Quicksort Screenshot 3

Quicksort Screenshot 3

The old pivot (8) is in the right partition but not yet in its final position in the list. The right partition will not be sorted until the left partition has been sorted recursively.

Quicksort Screenshot 4

Quicksort Screenshot 4


The old pivot (5) is in the right partition.
Both pointers coincide at the pivot and so each move one place. The value 2 does not appear
in either partition because it must be in its final position.  The left partition consists only of
one value (1) and so does not need to be sorted either.  

Quicksort Screenshot 5

Quicksort Screenshot 5

The right pointer is now less than the left index of the current list so the left partition is not sorted.

Quicksort Screenshot 6

Quicksort Screenshot 6

You should be getting the hang of this now!

Quicksort Screenshot 7

Quicksort Screenshot 7

Finally the right partition of the starting list can be sorted. The pivot (8) of the 3-value partition ends up by itself in the left partition.

Quicksort Screenshot 8

Quicksort Screenshot 8

We have tested this program with all 24 permutations of the list of numbers containing 1, 2, 3 and 4.

Quicksort comes into its own for large lists, when values move many places during a swap in the early stages. You will note that the final stages of quicksort involve a lot of comparisons, with data items moving a small number of places. It is possible to mix methods and to use insertion sort for the final stages.

Follow the links below to two demonstrations of this algorithm and one demonstration of a slightly different quicksort algorithm.

Programming - a skill for life!

Bubble sort, insertion sort, tree sort and quicksort