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)