CSC152 2006S, Class 49: Faster Sorts Admin: * Office hour signup outside office * Are there questions on Exam 3? * In an attempt at supporting today's protest, I will only hold half a class today. Overview: * Divide-and-Conquer Sorting. * Merge Sort. * Iterative Merge Sort. * Asymptotic Analysis of Merge Sort. * Quicksort. More Efficient Sorts * Sort more efficiently by "divide and conquer" * Two ways to divide: * First half vs. second half "Merge sort" * Smaller vs. larger C.A.R. Hoare "Quicksort" * Vector [23, 5, 1, 22, 0, 50, 18, 10] * Divide into two halves * First half [23, 5, 1, 22] * Second half [0, 50, 18, 10] * Sort the halves * F: [1,5,22,23] * S: [0,10,18,50] * Put them back together (Merge) * Take the smaller first element of either half * Result: [0, ...] * Lop off that element * F: [1,5,22,23] * S: [10,18,50] * Do it again * Result: [0, 1, ....] * F: [5,22,23] * S: [10,18,50] * Do it again * Result: [0, 1, 5, ....] * F: [22,23] * S: [10,18,50] * ... * When you run out of stuff in one part, shove the other part at the end * When we sort the halves, do it recursively * Base case: Empty: Sorted. // May not be necessary * Base case: One element: Sorted. * Running time? [See figure] O(nlogn) * Beats the O(n^2) for Friday's * Equal to Heapsort * Is this sorting algorithm stable? Can we make it stable? * Stable: Equal elements preserve order * If when we're merging, we take from the left half when confronted with equal elements, it's stable You can do a more formal analysis in combinatorics, using recurrence relations t(n) = n + 2*t(n/2) t(n) = n + 2*(n/2 + 2*t(n/4)) t(n) = n + n + 4*t(n/4) ... Other way to divide and conquer: By size (small and large) * Vector [23, 5, 1, 22, 0, 50, 18, 10] * Small: * Large for this list: 23, 22 * Small for this list: 5, 1 * new list: * Large: * Small: -1, -1000 * But what if the rest are all < -1000 * Need some context for determining large and small * Find largest O(n) * Find smallest O(n) * Average O(1) * Things smaller than average are small, things larger than average are larege * Try 1, 2, 4, 8, 16, 32, 4, 128, 256, 512 * Hoare's great idea: Guess the median, most of the time you're close * Chance is your friend * Empirical data support his claim * Two key ideas in Quicksort * Divide-and-conquer * Chance is your friend * Merging is easy in Quicksort: Concatenate * Phrased as divde-and-conquer * Pick a pivot * Split into small and large * Sort two halves * Concatenate Sam Rebelsky never logs out and [athanasa] doesn't have any lame ideas. Sad...