COMP1927 - Quick Sort

Quick Sort is a recursive divide and conquer sort.

It works by declaring a random point in the list the pivot and ensuring that everything is on the correct side of said pivot.

The list is then split into two halves (the two sides of the pivot) and the process is repeated.

## Type

Non-Adaptive; the number of swaps does change, and pivot changes it.

Stable

In-Place

## Complexity

Worst is O(n^{2}) – if it picks the worst pivot so that it’s going through n things, then n-1, then n-2, it becomes n^{2}

Best is O(lg(n))

Average is O(nlg(n))

## Example

## Code

void quickSort (int array[], int left, int right, int pivot); int pickPivot (int left, int right); void quickSort (int array[], int left, int right, int pivot) { // If we have two elements they may not be sorted, but less always is. if ((right-left) >= 1) { int leftCounter = left; int rightCounter = right-1; int temp; // This only works for pivot being rightmost, so we swap it there. temp = array[right]; array[right] = array[pivot]; array[pivot] = temp; pivot = right; // We have reached the middle, and hence stop // When the two counters meet while (leftCounter < rightCounter) { // We need to find a misplaced item in both left and right // <= means that all items == pivot are swapped to left side while ((array[leftCounter] <= array[pivot]) && (leftCounter<rightCounter)) { leftCounter++; } // At this point we have either found a misplaced left // Or left and right are equal so we never enter this while ((array[rightCounter]>array[pivot]) && (rightCounter>leftCounter)) { rightCounter--; } // Swap the two misplaced variables // As pivot is rightmost we don't worry about it if ((leftCounter < rightCounter)) { temp = array[leftCounter]; array[leftCounter] = array[rightCounter]; array[rightCounter] = temp; leftCounter++; rightCounter--; } } // Increment the left counter to find the first item >= pivot // If it is already greater than it, leave it alone // The problem with this is if the pivot is the biggest item // To account for this we tell counter to stop at the end // And then swap the pivot there (to the end) while ((array[leftCounter] < array[pivot]) && (leftCounter < right)) { leftCounter++; } // If our previous increment exceeded the array limits, we reset it if (leftCounter > right) { leftCounter = right; } // Swap the pivot into its correct position // i.e. swap it with the first element bigger than it temp = array[leftCounter]; array[leftCounter] = array[pivot]; array[pivot] = temp; pivot = leftCounter; // We call it with the max of left and pivot-1, // As if pivot = left, pivot-1 would go out of the bounds // Similarly with right and pivot+1 int newRight= max(left, pivot-1); int newleft = min(right, pivot+1); // When we've sorted this version of the list // (i.e. put the pivot in place) // We now call quick sort with the list to the left of the pivot // And with the list to the right quickSort (array, left, max(left, pivot-1), pickPivot(left, newRight)); quickSort (array, min(right, pivot+1), right, pickPivot(newLeft, right)); } }

page revision: 9, last edited: 09 Sep 2011 12:19