Quicksort

Along with Mergesort, Bubblesort and others, Quicksorting of arrays is a standard on any fully fledged undergraduate computer science course. It’s a simple theory, and like a lot of theories can be easily described verbally, on a whiteboard or even in pseudocode, but they all take a little work to actually implement. Quicksort is a "divide and conquer” comparison sorting algorithm. The basic idea is that you continually reduce the area of the array under inspection (or unsorted area) by arranging the values around a pivot value (which can be chosen randomly), and then doing the same to the left and right sub arrays in a recursive fashion. Acually Wikipedia explain this much better so here is their link. They also have a nice pseudocode version, repeated here: 

  function quicksort('array')
 if length('array') ≤ 1
 return 'array' // an array of zero or one elements is already sorted
 select and remove a pivot value 'pivot' from 'array'
 create empty lists 'less' and 'greater'
 for each 'x' in 'array'
 if 'x' ≤ 'pivot' then append 'x' to 'less'
 else append 'x' to 'greater'
 return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

It is common (and makes the explanation easy) to refer to dividing the array into left and right sub arrays or lists. In .Net you certainly could use lists, but it is much more efficient to use the same array, moving values and passing indices to inform each recursion of their sub portion of the array. In my implementation I use a class called Quicksorter, and calling QuickSort() on an instance of this class will trigger a call to the recursive method qsort passing the initial 0 and Length-1 parameters. 

  class QuickSorter
 {
 int[] intArray;
 
 public QuickSorter(int[] unsorted)
 {
 intArray = new int[unsorted.Length];
 unsorted.CopyTo(intArray, 0);
 
 }
 
 public void PrintArray()
 {
 for (int i = 0; i < intArray.Length - 1; i++)
 {
 Console.Write(intArray[i] + ", ");
 }
 Console.WriteLine(intArray[intArray.Length - 1]);
 }
 
 public void QuickSort()
 {
 qsort(0, intArray.Length - 1);
 }
 
 private void qsort(int left, int right)
 {
 int pivot, lft, rgt;
 
 lft = left;
 rgt = right;
 pivot = intArray[left];
 
 while (left < right)
 {
 while ((intArray[right] >= pivot) && (left < right))
 {
 right--;
 }
 
 if (left != right)
 {
 //now we know the rhs value is less than the pivot, so move it (left was saved as the pivot value)
 //and move the lhs counter after the operation
 intArray[left++] = intArray[right];
 }
 
 while ((intArray[left] <= pivot) && (left < right))
 {
 left++;
 }
 
 if (left != right)
 {
 //now we know the lhs value is greater than the pivot, so move it, rhs is pointing to a value which has been copied/duped to the lhs, basically a free space
 //and move the rhs counter after the operation
 intArray[right--] = intArray[left];
 }
 }
 
 //pivot value can slot back in to the free/duplicate lhs space
 intArray[left] = pivot;
 
 //reset lhs, rhs and pivot
 pivot = left;
 left = lft;
 right = rgt;
 
 if (left < pivot)
 {
 qsort(left, pivot - 1);
 }
 
 if (right > pivot)
 {
 qsort(pivot + 1, right);
 }
 }
 }

This class could easily be adapted for other value types and could easily be altered to sort arrays of any object by:

1. a) Implementing the IComparer interface
2. b) Changing the comparison lines to use the results of .Compare(object1, object2)

Comments

• Anonymous
  March 18, 2013
  And if you're really interested in sorting algorithms, check this out - this page pulls javascript sorting algorithms from stackoverflow: gkoberger.github.com/stacksort