CSC151 2007S, Class 47: Introduction to Sorting Admin: * Updated instructions for submission of project * Are there final questions on the project? * I know that there have been some problems with region.compute-pixels! I do not know how to resolve those problems efficiently. * Exam 3 will be distributed tomorrow. * Intentional mostly-talk class. (No lab!) * EC: Percussion Ensemble 7:30 p.m. Friday (we think) * EC: Women's Basketball 5:30 p.m. Friday vs. St. Norbert * EC: Women's Basketball 1:00 p.m. Saturday vs. Carroll * EC: George Cobb Statistics talk Monday noon Overview: * The problem of sorting. * Writing sorting algorithms. * Examples: Insertion, selection, etc. * Formalizing the problem. /What did we do on Tuesday?/ * Binary search things * A technique for searching in which you look at half of the region at once * Works with vectors (not lists) * Look at the middle and throw away half. * A lot faster than looking at the elements one by one * In order to use binary search, the vector must be in ascending order *ANd you must be able to test for comparison In order for binary search to work, the vector must be in order. /THe problem of sorting: How?/ i * Given a list or vector in no particular order, how do you get it in order? * Lists: Build a new, sorted version * Vectors: Rearrange * What techniques do we have for coming up with algorithms? * Think about it * Relate it to something you know how to do * In "the real world" * Previous algorithms you've written to solve similar problems * Or that someone else has written * Make sure that you understand the problem well * Try to execute possible steps by hand * Look at other solutions (not useful if you're solving something new) * Look at common algorithm design techniques First technique (credit to Lee and Gumm)a * Insertion sort * Separate your data into two parts: Unsorted and sorted * Repeatedly * Grab one element from unsorted * Put it in the right place in sorted * Bucket sort (credit to Decker) * Pick logical groups into which to partition elements (months for sorting by date, height ranges for sorting by height ...) * Put each element into the proper group * And then sort each group * Selection sort (credit to Doers) * Repeatedly * Select the largest remaining element * Put it at the end Time to write one of these in Scheme. ;;; Procedure: ;;; list.sort ;;; Parameters: ;;; lst, a list to sort ;;; may-precede?, the order in which to sort (define list.sort (lambda (lst may-precede?) ...)) Time to call it > (list.sort (list 156 2 1 5 8) <=)