CSC153 2004S, Class 24: 'Fast' Sorting Algorithms Admin: * Other ways that Grinnell differs from UofC * Students and faculty don't interact informally, like they do in this class. * Open curriculum vs. "the model core curriculum" * Exam forthcoming. (Previous exam returned before next exam given.) * Some of next class will be about the exams * Next week in Science Teaching and Learning Group: How much work do you give your students? * Claim: Students have twenty hours per week, if you count the time-consuming musical groups and labs in which they participate. (20) * Revised: 16 hours per week in class * If faculty assume that students study three hours outside of class per hour in class, that's sixty hours. (60) * Revised: 48 hours per week in class * If you eat two hours each day (14) * If you shower and stuff one hour each day (7) * If you work to afford Grinnell (20) * If you exercise 1 hour each day (7) * That's 128 hours * Revised: 112 hours * There are 168 hours in a week. * 40 hours to sleep and socialize per week. If you just slept, you'd get 6 hours per night. * Revised: 56 hours, 8 hours sleep per night * Conclusion: * Choose between musical groups, lab science, and sleep * Choose between work and socialization Overview: * Consider how to apply the "divide and conquer" technique to sorting * Key ideas in merge sort. * Key ideas in Quicksort * Lab (to be continued next class) Reminder: When trying to solve a problem (either better or new): * Consider similar problems you've solved already * Try it "by hand" and generalize * Apply common algorithm design strategies * ... Observation: Both sorting algorithms you've learned in this class are O(n^2) * Insertion sort * Selection sort * Repeatedly grab the smallest/largest remaining element and shove it at the front/end * Bubble sort is also O(n^2); it is almost always the slowest n^2 sorting algorithm. * In the abstract, bubble sort is nice to parallelize (Parallel bubble sort on n computers is O(n), which is pretty good) Question: Can we do better?