CSC153 2004S, Class 23: Sorting
Admin:
* Two readings: Merge sort and Quicksort.
* Have a great weekend. No new homework!
* Is "I don't plan to make it to my classes because I have too much homework" a good excuse for missing class?
* (I do appreciate the notification, though.)
* It's about prioritization: If your grade depends on a paper that has to get done, then you sometimes have to miss class.
* Sam as teacher: Good students plan ahead.
* Sam as human: Makes sense to me.
Overview:
* The "Batman" problem.
* Rephrasing and rewriting binary search without getkey.
* Designing algorithms.
* The problem of sorting.
* Two solutions: Insertion sort and merge sort.
* More time for searching lab (if there's time)
/The Batman Problem/
* Why does the following happen?
> (binary-search "Batman" cartoons car string (binary-search "Batman" cartoons car string<=?)
-1
* Request: Extend the code to see what happens?
* Observation:
(cond ((comes-before? key middle-key)
(search-portion lower-bound (- midpoint 1)))
Says "If they're equal, throw away the middle element and recurse" (but only if comes-before? permits equality).
* Is that result acceptable?
* Unacceptable: 2
* Acceptable: 1 (if the preconditions specify stuff well), 1, 1 (preconditions; would prefer that it did work)
* Can we rewrite binary search so that it accepts a <= predicate?
* Need to check equality separately: If we want to check equality separately, we need an equality predicate.
* Or ... (if (and (comes-before key midkey) (comes-before midkey key)) ...) (and preconditions that when comes-before is reflexive, the two values must be equal)
/How can we rewrite binary search without including get-key?/
* Could make the "what to match" parameter a procedure that accepts or rejects things
* Could make the comes-before? predicate extract the car.
* But how will it compare a procedrue (the "what to match" parameter) and a list?
* One possibility: "What to match" parameter can be a list (or whatever type the elements of the vector to search are)
* First: What would the "Search for Batman" call look like in such a procedure?
(new-binary-search ("Batman", "???") cartoons
(lambda (toon1 toon2)
(string