Quicksort Overview

Quicksort is a recursive sorting algorithm that sorts an array of elements in place. It does not need extra space to copy temporary arrays like merge sort, and usually has good performance. For Lab 03, we will provide the pseudocode for quicksort and you will need to implement and test the quicksort algorithm in C++.

Quicksort uses a subroutine known as partition that picks one element p in the array to use as a pivot and then partially rearranges the elements in the array such that all elements smaller than or equal to the pivot are to the left of the pivot, and all larger elements are to the right of the pivot. After a single partitioning step, the algorithm recursively sorts the sub-arrays to the left and right of the pivot.

We first outline this partitioning step

partition(A, start, finish):
  Input: an array A and integer indices start and finish denoting a sub-array of A.
  Output: returns the index of the pivot element and partitions A such that all
   items less than or equal to the pivot are to the left of the pivot, and all
   items greater than the pivot are to the right. 

  /* choose a pivot element by selecting the last element
     in the sub-array A[start..finish] (inclusive) */
  pivot = A[finish]
  left = start
  right = finish-1
  while left <= right
    if A[left] <= pivot
      //small items don't need to move right
      left++
    elif A[right] > pivot
      //big items don't need to move left
      right--
    else
      //swap a big item on the left with a small item on the right
      swap(A, left, right)

  //move the pivot to the right spot
  swap(A, left, finish)
  return left //return index of final pivot location

With partition as a building block, we can define a recursive function quicksort that sorts a sub-array A[left..right].

quickSort(A, left, right):
  Input: an array A and integer indices left and right denoting a sub-array of A.
  Output: Returns nothing, but modifies the elements in A[left..right]
  so they are sorted in ascending order. 

  if right > left
    idx = partition(A, left, right)
    quickSort(A, left, idx-1)
    quickSort(A, idx+1, right)

Usually, we think of a sort function as simply taking an array and its size as input. We can write a version of quickSort with this prototype as well using a small wrapper.

qsort(A, n):
  Input:  an array A of n elements
  Output: Nothing, but array A is sorted in ascending order after the function call

  quickSort(A, 0, n-1)

Practice

Show the output of partition on the array [3,9,4,15,7,1,8,6]. What is the final location of the pivot 6?

Runtime and Correctness

We will likely not have time to go through a detailed analysis on the run time and correctnes of quicksort, but you should verify experimentally that the algorithm is correct and usually pretty quick.