One solution is to use a slightly different algorithm and not move the pivot on the left pointer at all. This stops the scans from hanging when there are duplicate pivot values but the whole procedure now hangs if the pivot is either the maximum or minimum in the array. The reason is simply that to cure the one problem we have gone back to splitting the array into two portions and when the pivot is the maximum or the minimum one of the portions is null and there is no change.

There are a number of solutions to this problem and most of them are radical. However there is a simple modification to the classical approach that still splits the array into three parts and copes with multiple values of the pivot. All you have to do is test for the L and R pointers to be both pointing at the pivot and don’t repeatedly swap the values. Instead all you have to do is move the L pointer on to the next value. What sort of division does this weird modification to the pure algorithm produce?

Well, the unsatisfying answer is that when the pointers meet all of the values to the left of the L pointer are less than or equal to the pivot, all of the values to the right of the L pointer are strictly greater than the pivot and the value pointed at by L is the pivot and it is in the right place. This means that we still have a three-part division and the array always shrinks even if the pivot is chosen to be the maximum or minimum value.

Failing algorithms

The implementation

At last we have a practical although not very elegant algorithm.

To make sure that the algorithm is 100% accurate let’s implement it using C# – although translation to other languages is easy.

Start a new project and place a single button on the form. 

The sequence of events is to generate some data, sort it and print it:

const int n=50;

private void button1_Click(
   object sender, RoutedEventArgs e)
{
 int[] data=setdata(n);
 quicksort(0,n-1,ref data);
 printdata(data);
}

We now have to write each of these routines and the routines that they use.

The setdata routine is a simple shuffle of integer data. You should try other types of data including datasets with repeated pivots just to check that it all works.

int[] setdata(int n) {
 int[] data=new int[n];
 Random R=new Random();
 for(int i=0;i<n;i++)
 {
  data[i]=i;
 }
 for(int i=0;i<n;i++)
 {
  swap(ref data[i],
       ref data[R.Next(n-1)]);
 }
 return data;
}

The first for loop simply generates an array of data in order 1 to n. The second for loop then swaps each element with a randomly generated element. We need to write the swap routine but as this is used within the quicksort itself this can wait till later. 

<ASIN:157586326X>

<ASIN:1848000693>

<ASIN:0470121688>

<ASIN:0201558025>

<ASIN:1565924533>