QuickSort Exposed
Written by Mike James   
Thursday, 24 June 2021
Article Index
QuickSort Exposed
The Quicksort Division
The Subtle Pivot
Recursive Routine

 

The quicksort routine does all the work and, of course it is recursive:

void quicksort(int start,
                  int finish, ref int[] data)
{
 if (start >= finish) return;
 int L=start;
 int R=finish;
 int pivot = data[start + (finish - start) / 2];
 scan(ref L,ref R,pivot,data);
 while(L!=R)
 {
  swap(ref data[L], ref data[R]);
  if(data[L]==pivot && data[R]==pivot)L++;
  scan(ref L,ref R,pivot,data);
 }
 quicksort(start,L-1,ref data);
 quicksort(R+1,finish,ref data);
}

 

You can see that, as explained in the description of the algorithm, what happens is that the pivot is selected as the value roughly in the middle of the array and then a scan and swap operation is repeatedly performed. Note, there are lots of better ways of choosing a pivot. 

When the pointers meet the loop ends and there is no need to perform a swap. The final If statement in the loop checks to see if the L and R pointers are both stuck on a pivot and if so moves the L pointer on by one.

Finally the recursive calls to the quicksort sort the left and right portions of the array. Notice that as the calls use “start to L-1” and “R+1 to finish” the recursive calls are guaranteed to finish because the array always grows shorter by at least one and it is assumed that it contains the pivot value.

Finally we need the scan routine –

void scan(ref int L,ref int R,int pivot,int[] data)

{
 while (data[L] < pivot)
 {
   L++;
   if (L == R) return;
 }
 while (data[R] > pivot)
 {
   R--;
   if (L == R) return;
 }
}

You can see that this scans from the left and from the right until either the pointers meet or it sets the L pointer to the first value greater than or equal to the pivot and the R pointer to the first value smaller than or equal to the pivot. 

All we need to complete the program are some trivial utility routines the swap routine:

void swap(ref int a, ref int b)
{
 int t = b;
 b = a;
 a = t;
}

And the print data routine:

void printdata(int[] data)
{
 for (int i = 0; i < n; i++)
 {
   Console.WriteLine(data[i].ToString());
 }
}

Now you can try it all out.

It works and it works with repeated values, repeated pivots, all values identical and it works if the array is already sorted. It does work fast but notice that for small and special forms of data other sort routines can be faster – QuickSort shows its worth when you have lots of data to be put into order.

You can even make QS faster by using an alternative sorting method when the size of the sub array reaches a set size. You can tinker with it to improve its performance to your heart’s content – clearly if you really are after speed then you should implement it in a more efficient language such as C/C++ or better use a tried and tested routine rather than creating your own.

As always it is worth saying that it is always better to get hold of a proven implementation of any algorithm rather than implementing your own. In this case the interest is in knowing how it works. 

What is really surprising is how sensitive the QS algorithm is to the exact implementation. What appear to be very small changes in the algorithm, or in the assumptions about the data, produce something that doesn’t work in a big way!

 

It's all about the pivot value and how it gets moved into the correct location. 

 

If you would like the source code of this projectvisit the CodeBin

Related Articles:

Quick Median       

Sorting Algorithms as Dances       

Silverlight Sorting Lab

Magic of Merging

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


CSS Test of Time Award 2023
18/02/2024

The ACM CCS Test-of-Time Award honors research with long-lasting influence, which have had significant impacts on systems security and privacy. The 2023 award in respect of a paper by Marten van Dijk  [ ... ]



Flox Releases Flox Hub
13/03/2024

Flox has announced that its Command Line Interface (CLI) and FloxHub are now generally available. The CLI is open source and FloxHub is free for anyone to use.


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

Banner


The Minimum Spanning Tree - Prim's Algorithm In Python

Finding the minimum spanning tree is one of the fundamental algorithms and it is important in computer science and practical programming. We take a look at the theory and the practice and discover how [ ... ]



AWS Low Cost Mailing List Using phpList And SES

Running a mailing list is not easy or cheap, but if you use AWS it can be. Find out how to create a low-cost and highly effective mailing list server.


Other Projects

<ASIN:076375756X>

<ASIN:0201118890>

<ASIN:0201485419>

<ASIN:0763707821>

<ASIN:0471327107>

<ASIN:0201000237>

<ASIN:0521663954>

<ASIN:0596514808>

 



Last Updated ( Thursday, 24 June 2021 )