The quick sort

The simplest way to describe how quick sort works is by way of an example. 

Starting with a list of number that you want to sort

       2  4  6  3  7  9  1

step one is to pick a value to act as a “pivot”.  It is usual to pick one of the numbers that are actually in the list but this isn’t essential and it often leads to a misunderstanding of  the overall method. However let’s stick with tradition and pick a roughly “middle” value, 3 say.

      2  4  6  3  7  9  1
               ^
             Pivot

Step two uses the pivot value to divide the list into two parts. Values smaller than the pivot are moved to its left and values larger than the pivot are moved to its right.

        2  1  3  7  9  6  4
              ^
             Pivot

Now you can see that the list is divided into two parts – values less than or equal to the pivot and values that are greater than the pivot –

         <=    |     >
       2  1  3  7  9  6  4
             ^
           Pivot

How does this help?

The list clearly isn’t fully sorted but you should be able to see that to put it into order there is no need to move any elements between the two parts.

The values bigger than the pivot may have to be rearranged to put the list in order but they don’t have to be swapped with any element in the “less than or equal to” portion. They might not be in exactly the right place but they are in the right “half” of the list.

As you only need to examine each value once and move it to its new location in theory the splitting should be possible to achieve in O(n) operations and so repeating the action until we reach a list with only one element – which is obviously in order – gives an algorithm that works in O(nlogn) which is a lot better than O(n^2) of most sorting algorithms.

Notice that there is no need for the pivot to be a value in the list of numbers the method still works. It still divides the list into values less than or equal to the pivot and greater than the pivot.

Of course for the method to be efficient the pivot should divide the list into two equal halves – and this means it is a good idea to choose a value that is in the list.

Practical in-place QS

That’s it. That’s all there is to the QS method – but in this form it isn’t very practical. The biggest problem is that we haven’t given an exact algorithm for doing the division and if possible this should be an “in-place” algorithm which sorts the values using nothing but the array that they are supplied in.

An “in-place” algorithm suggests that we need to use something that swaps values that need to be moved to opposite ends of the array. There is a sense in which this "swap" algorithm is an additional idea to the divide and conquer principle that gives us our basic quick sort as described so far. 

Consider the following swap algorithm:

1. Start off from the left hand end of the array and scan along until you find the first value bigger than the pivot.
2. Next scan from the right hand end of the array until you find the first value smaller than the pivot.
3. Swap the two values and continue the scan from the left and the right.

This simple description hides a lot of detail.

The main problem is when does the scan stop and where is the division point for the array, i.e. where is the location that divides the list into values less than or equal to the pivot and values larger than the pivot?

<ASIN:0471327107>

<ASIN:0201000237>

<ASIN:0521663954>

<ASIN:0596514808>