week2/14-quicksort

Quicksort

Wikipedia on Quicksort.

Algorithm

Another divide-and-conquer algorithm, Quicksort works by picking a pivot point, or a value in the array, and reordering all the elements with values less than the pivot to the front of it, and all values greater than the pivot to the back. This is called the partition operation, and upon completion the pivot point is in its correct position.

You then recursively apply the same steps to each sub array - the elements smaller than the last pivot, and the elements larger than the last pivot.

Your base case is when a sub array is length 1 or 0.

The Pivot

Unsure of where to set the pivot? Read under the header "Implementation issues" on the Wikipedia.

Implementation

Write a function, quicksort() that takes an unsorted list and returns a sorted list. You may want to use some helper functions to partition.