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)