« What The Sony PSP Really Needs | Home | Are you a programmer with free time? »

Lessons In Algorithms: Quicksort

This is the second article in the Lessons In Algorithms series here at The Angry Walrus. The first article was about the binary search algorithm.

The Vitals:

1. Category: Sort Algorithm
2. Name: Quicksort
3. Data Structure Used: Array
4. Speed: O(nlogn)

The Algorithm

Quicksort is an unstable comparison sort algorithm that is widely known within computer science, as it is one of the most widely used sorts available. It was developed by Charles Antony Richard Hoare, a British computer scientist, in 1960. In has an average running time of O(nlogn), with a quadratic run time (O(n^2)) being the worst case scenario. Quicksort’s strengths and weaknesses vary by implementation – but it’s obviously more complex at the base level than any quadratic sort algorithm for it’s use of recursion. In the final implementation I created below, based on the Wikipedia pseudo code, I made use of ‘in place partitioning’, which allowed me to save space(memory).

How it works

The basic quicksort works by breaking the original array into smaller arrays – which then are further dealt with via recursion. This is known as a ‘divide in conquer’ strategy. An element known as the ‘pivot’ is chosen, and all values greater or less then the pivot value are moved appropriate to the left or right of the pivot value – so the pivot ends up in the middle with concatenation. This partitions the array in such a way that lower values are on the left, and larger ones are on the right. The list is then recursively subdivided further until it becomes sorted.

The version I decided to implement, as I earlier mentioned, uses an ‘in-place’ partitioning algorithm. This means that instead of creating an array of values greater and less than the pivot and then joining them with concatenation – all the operations are done inside the same array. Essentially, the same process happens in both the basic, and ‘in-place’ versions of the partition algorithm. The only difference being that the ‘in place’ version is a bit more clever. To show you a better idea of what’s going on in the ‘in-place’ partition step, I borrowed the picture on the left from wikipedia. The boxed number represents the pivot value, the blue numbers represent the values that are less than or equal to the pivot, and the red numbers are greater than the pivot value. Note the last step in the process, where the pivot is placed where the values go from blue(less) to red(greater).

Here is a simple implementation of the in-place partition done in C++. Included also, is a helper function that will ’swap’ two items.

//swap function (pass by reference)
void swap(int *Pa, int *Pb){
     int temp = *Pa;
     *Pa = *Pb;
     *Pb = temp;
}//end swap function
 
//partition function (in place partitioning)
int partition(int array[], int left, int right, int pivotIndex){
    int pivotValue = array[pivotIndex];
    swap(array[pivotIndex], array[right]);
    int storedIndex = left;
    for(int i = left; i <= (right - 1); i++){
        if(array[i] <= pivotValue){
            swap(array[i], array[storedIndex]);
            storedIndex += 1;
            }//end if
    }//end for
    swap(array[storedIndex], array[right]); // pivot moves
    return storedIndex;
}//end partition function
 
//sort function
void quicksort(int array[], int left, int right){
     if(right > left){
              //choose pivot (I'll pick left)
              int pivotIndex = left;
              int newPivotIndex = partition(array, left, right, pivotIndex);
              quicksort(array, left, newPivotIndex - 1);
              quicksort(array, newPivotIndex + 1, right);
 
          }//end if
}//end quicksort

Similar Posts:

• Lessons In Algorithms: Binary Search