QuickSort

README.md

QuickSort

QuickSort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. It is also known as partition-exchange sort because of its use of the partition algorithm. In the worst case, it makes O(n2) comparisons, though this behavior is rare. QuickSort is often faster in practice than other O(n log n) algorithms.

Partition Algorithm

We know that QuickSort relies on partitioning as a key step in its algorithm, but what does that really mean? Here is an annotated version of the code for partition.

public static int partition(int[] array, int pivot, int lo, int hi) {

       // get the value of the element at the pivot point
       int pvalue = array[pivot];

       // repeat some steps until our lower bound is greater than our upper 
       // bound
       while (lo < hi) {

       	     // increase our lower bound until we get to an element that is
	     // greater than our pivot value
	     while (array[lo] < pvalue) lo++;

	     // decrease our upper bound until we get to an element that is
	     // less than our pivot value
	     while (array[hi) > pvalue) hi--;

	     // now that we have something at lo that is greater than our
	     // pivot value and something that hi that is less than our pivot
	     // value, we must swap them in order to satisfy our partitioning
	     // scheme
	     swap(array, lo, hi);

       } // while

       // when the lower bound is greater than the higher bound, we are
       // confident that everything to the left of lo is less than everything
       // to the right of lo. 

       // return lo as the new pivot location
       return lo;

} // partition

Once you've read the annotated code for partition it's relatively easy to see what it's doing. Given an array and a pivot point, the algorithm swaps elements in the array such that all elements in the array that are less than the original pivot value come before it and all elements that are greater than the original pivot value come after it.

There are a couple different ways to implement partitioning. The implementation provided above is your teacher's favorite because it's performed in place (does not require another array) and requires only O(log n) space.

QuickSort Algorithm

The actual QuickSort algorithm as implemented on your exam is very similar to BinarySearch. Here is an outline of the algorithm as well as some annotated code.

1. Determine the midpoint of your seach space (e.g., mid = lo / 2 + hi / 2).
2. Partition your array using that midpoint as your pivot point and replace your original midpoint value with the value returned by partition (e.g., mid = parition(array, mid, lo, hi)).
3. QuickSort the left partition (e.g., quicksort(array, lo, mid - 1)).
4. QuickSort the right partition (e.g., quicksort(array, mid + 1, hi)).

Here is the annotated source code:

public static void quicksort(int[] array, int lo, int hi) {

       if (lo < hi) {

              // determine the midpoint
	      int mid = lo / 2 + hi / 2;

	      // partition the array using the midpoint as the pivot point. replace the
	      // midpoint with the value returned from partition
	      mid = partition(array, mid, lo, hi);

	      // quicksort both partitions
	      quicksort(array, lo, mid - 1);
	      quicksort(array, mid + 1, hi);

       } // if

} // quicksort

In the implementation described above, the pivot value that is passed to the partitioning algorithm is simply chosen to be the midpoint within the current search space. In practice, however, the pivot value is chosen randomly from within the current search space. This causes the QuickSort algorithm to have an expected running time of O(n log n) after performing a probabalistic algorithm analysis. You'll probably hear more about this in the Data Structures, and I certainly hope that you both hear about and see the actual analysis in the Algorithms course.