CSC151 2007S, Class 47: Quicksort

Admin:
* Your TA is much too nice.  Sam won't call absent people.
* Are there questions on HW16?
  * Do I need a helper to find the index of the smallest value?
    * You're dealing with vectors, and we almost always write helpers
      for vectors because we recurse over the index
* EC for tomorrow's convo.
* No softball today (so no EC).
* Shift in next week's topic.
  * Sam needs to change grading strategies. Done.
  * Sam needs to grade your first project reports.  Whoops!

Overview:
* The key ideas of Quicksort.
* Lab.

/Quicksort/

* A new way of sorting
  * Divide and conquer - Split the collection into two parts, sort
    each half, and join together
  * Split the list into smaller values and larger values
    * Saves you a lot of comparisons
    * Easier to merge
  * Pick a pivot, which you use to divide the list into smaller and larger things
  * The pivot is randomly selected, because finding the median is hard
* Critique: What if you choose a really bad pivot, won't your sorting algorithm suck?  
  * If you always pick a bad pivot, this isn't much of a gain.
* Potential improvement: Why not pick two pivots and average them?
  * It's another step.
  * For lists of integers, you might not end up with an integer, unless
    you used quotient.
  * Not necessarily more central: If you pick the middle element and the largest element, their average is farther from the middle than the middle.
  * Averaging doesn't work for non-numbers
* Why not average largest and smallest?
  * Cyrus's complaint
  * (1 2 4 8 16 32 64 128 256)
* Potential improvement: Pick three pivots and then use the middle one

/Lab/

/Why Can't You Use <=/

* Why does (Quicksort grades <=) recurse forever while (Quicksort grades <) terminate?
  * Something to do with the pivot that is difficult to articulate; perhaps the pivot is too emotional (or at least sentient and malicious)
  * If you use <=, partition builds (less-than-or-equal-values EMPTY greater-values)