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?