Back

Quicksorting

Quicksorting
A very quick way to sort a set of data is to use the quicksort algorithm. The algorithm performs the following functions on a set of data:

• • It selects one of the pieces of data in the set of data to be sorted, called the ‘PIVOT’.
  • It makes a pass through all the data items. At the end of the pass, three things will have happened:

• • • The PIVOT will be positioned correctly.
    • Data items less than the PIVOT will be on the left of it.
    • Data items greater than the PIVOT will be on the right of it.
• • The quicksort algorithm is then applied recursively to the left of the PIVOT.
  • The quicksort algorithm is then applied recursively to the right of the PIVOT.

An example of the quicksort algorithm
One slightly confusing aspect of quicksort is that sometimes we need to look at the actual data and sometimes we need to look at pointers that point to the position of a data item.

It is very important to know whether you are looking at the position of a piece of data (given by the pointer) or the actual data at the position pointed to by the pointer!!

The best way to understand how quicksort works is to do an example. Imagine you want to sort these nine numbers:

What variables and pointers do we need?
We are going to need two variables and two pointers.

• • We will need a variable to hold the first value, called FIRST.
  • We will need a pointer that points to the position of data as we move through the data from left to right. We will call this pointer UP.
  • We will need a pointer that points to the position of data as we move from right to left through the data. We will call this pointer DOWN.
  • We will need a variable to hold something called the PIVOT.

We now have:

What actually happens when you call the quicksort procedure?
A slightly more detailed pseudo-code description of what quicksort does is as follows:

1. If the number of data items to be sorted is greater than one then
     2. Make the PIVOT equal to the first piece of data in the set of data we want to sort.
         3. Make FIRST equal the first piece of data in the set of data we want to sort.
         4. Make UP the position of the first piece of data.
         5. Make DOWN equal the position of the last piece of data.
         6. REPEAT
               7. Increment UP until you find the data pointed to by UP that is greater than the PIVOT value
                   (or until you get to the last  position).
               8. Decrement DOWN until you find the data pointed to by DOWN that is less than or equal to the PIVOT.
                   (Always start by checking the actual value pointed to by DOWN first!)
               9. If the pointer UP is less than pointer DOWN then
                       10. Swap the data pointed to by those pointers.
              11. End If
       12. Until (UP meets DOWN) or (UP passes across DOWN).
       13. Swap FIRST with the data item pointed to by DOWN.
       14. Set PIVOT equal to the value pointed to by DOWN.
15. End If.

Let’s work through the example!
After lines 1 to 5 in out pseudo-code, we have:

We now need to do the pseudo-code in lines 6 to 14. Increment UP until UP is greater than PIVOT. The first piece of data that is greater than 42 is 70. Decrement DOWN until the data pointed to by DOWN is less than or equal to PIVOT. In fact, 30 is the first piece of data that is less than or equal to 42. We now have the following:

UP is less than DOWN (2 < 9) so we swap the data in position 2 with the data in position 9, to give:

Continue!
The pointers UP and DOWN haven’t met and neither have they crossed over.  We are therefore still inside the REPEAT construct. We need to continue as before. We continue to increment UP until we find the next piece of data where UP is greater than PIVOT. UP is at position 5 (data 51) when this occurs. We decrement DOWN until we find the first piece of data where DOWN is less than or equal to PIVOT. DOWN is at position 6 when this occurs (data 10). We then exchange their values because UP is less than DOWN. We now have this:

And continue again!
The pointers UP and DOWN haven’t met and neither have they crossed over.  We are therefore still inside the REPEAT construct. We need to continue as before. We increment UP until we find the first piece of data where UP is greater than PIVOT. UP is at position 6 (data 51) when this occurs. We decrement DOWN until we find the first piece of data where DOWN is less than or equal to PIVOT. DOWN is at position 5 when this occurs (data 10). We do not exchange the data values at positions UP and DOWN this time because UP is not less than DOWN. We now have this:

UP has actually passed across DOWN. This is one of the exit conditions of the REPEAT construct in line 12 of our pseudo-code. We therefore drop out of the REPEAT loop. Line 13 of the pseudo-code says to swap FIRST with the data item pointed to by DOWN. Line 14 of the pseudo-code says that PIVOT should then be given the value pointed to by DOWN. This gives us:

PIVOT = 42 (which, in this case, just so happens to be what it was before!)

Something important to note!
All the data values to the left of the PIVOT value are less than the PIVOT value. All of the values to the right of the PIVOT value are greater than the PIVOT value. This means:

• • The PIVOT value is now in exactly the correct place if, for a moment, we assumed that all data items were now ordered correctly.
  • There is an unordered set of data items to the left of the PIVOT. These data items are all less than the PIVOT value.
  • There is an unordered set of data items to the right of the PIVOT. These data items are all more than the PIVOT value.

We can represent this as:

Now work on the left hand side.
What we can now do is treat the left hand set of data items as a completely independent set of data that needs sorting using the quicksort algorithm again! We call the quicksort algorithm again (recursion) and continue.

Increment UP until it is greater than PIVOT. UP equals 2 (data 30). Decrement DOWN until it is less than or equal to PIVOT, as before. DOWN therefore equals 1 (data 10).

Continue!
We don’t exchange the data items pointed to by UP and DOWN because the pointer UP is not less than the pointer DOWN. We have met one of the exit conditions for the REPEAT loop and so we exit the loop. We exchange FIRST and DOWN (so in this particular case they stay the same because FIRST and DOWN have the same value). PIVOT is then given the value of the data pointed to by DOWN, which is 10 (the same as it was before). PIVOT is now in the correct place if all of the data were in order.

There aren’t any data items to the left of the PIVOT so there isn’t a left hand side of the PIVOT to work on. However, there is more than one piece of data to the right of the PIVOT. We therefore quicksort the right hand side. We call the quicksort algorithm again (recursion) and continue. We now have:

Incrementing UP until the data item pointed to by UP is greater than PIVOT, we get UP equals 3 (data 40). Decrementing DOWN until the data item pointed to by DOWN is less than or equal to PIVOT, we get DOWN equals 2 (data 20). We don’t exchange the data items pointed to by UP and DOWN because the pointer UP is not less than the pointer DOWN. Because UP and DOWN have crossed, however, we must swap FIRST with the data item pointed to by DOWN and then PIVOT is given the data item pointed to by DOWN. PIVOT is now in the correct place if all the data were in the correct order. We now have:

Remember!
Just to remind you, after every quicksort pass

• • The PIVOT value is in the right place.
  • All data to the left of the PIVOT are less than the PIVOT.
  • All data to the right of the PIVOT are greater than the PIVOT.

The left hand side of the PIVOT has only one data item and so doesn’t need quicksorting. This also applies to the right hand side of the PIVOT. These three data items must therefore be sorted in order!

So, we started with:

and quicksorted them into:

A summary so far.
To summarise what we have done so far, we started with this:

And quicksorted it into this:

We then recursively called quicksort to sort the left hand side of the PIVOT, to get this:

We now need to quicksort the right hand side. 

Quicksorting the right hand side.
Remember to follow the algorithm! It is a very mechanical process.

UP is incremented until the data it is pointing to is greater than the PIVOT. UP is incremented until it equals 2. Down is decremented until it points to a piece of data that is less than or equal to the PIVOT. Down is decremented until it equals 1.

The pointer UP is not less than the pointer DOWN so they are not swapped. UP and DOWN have crossed over so you exit the REPEAT loop. FIRST is swapped with the data item pointed to by DOWN (they both are 51 in this particular case). PIVOT is set to DOWN, which is 51 (which just happens to be what it was before).

Continue!
We now have a PIVOT value of 51. There aren’t any data items to the left of the PIVOT so there isn’t a left hand side of the PIVOT to work on. However, there is more than one piece of data to the right of the PIVOT. We therefore quicksort the right hand side.

UP is incremented until the data it is pointing to is greater than the PIVOT. UP is incremented until it equals 2. Down is decremented until it points to a piece of data that is less than or equal to the PIVOT. Down is decremented until it equals 1.

The pointer UP is not less than the pointer DOWN so they are not swapped. UP and DOWN have crossed over. FIRST is swapped with the data item pointed to by DOWN (they both are 61 in this particular case). PIVOT is set to DOWN, which is 61 (which just happens to be what it was before).

And again!
We now have a PIVOT value of 61. There isn’t a left hand side so we quicksort the right hand side by calling the quicksort algorithm recursively again.

UP is incremented until the data it is pointing to is greater than the PIVOT (or you get to the last position). UP is incremented until it equals 2 (the last position). DOWN is decremented until it points to a piece of data that is less than or equal to the PIVOT. In fact, DOWN stays at the value 2 because 70 is less than or equal to the PIVOT. Both UP and DOWN now equal 2.

The pointer UP is not less than the pointer DOWN (they are both the same). The pointer UP has met the pointer DOWN. This is an exit condition for the REPEAT loop. FIRST is now swapped with the data item pointed to by DOWN so is given the value 70. PIVOT is then set to the data item pointed to by DOWN, which is 70.

We now have the data in this order:

We have a PIVOT value 70. There isn’t a left hand side of the PIVOT and the right hand side only has one piece of data, so we have finished quicksorting this data.

Now recombine all of the recursive calls.
We started with this:

And we have ended with this:

Back