COMP1927 - Quick Sort

Sorting_quicksort_anim.gif

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(n2) – if it picks the worst pivot so that it’s going through n things, then n-1, then n-2, it becomes n2

Best is O(lg(n))

Average is O(nlg(n))

Example

pic1.jpg

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));
 
   }
 
}