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