CSC151 2009F, Class 46: Introduction to Sorting Admin: * Reading for Tuesday: Sorting, * Revisits the topics of today's class in more detail. * Quiz 11 returned * Depressing: * (a) Many forgot what assoc does * (b) Even though acronym was on the lab, many solutions were wrong * (c) We screwed up the order of parameters to assoc * Because of (c), I've added 2 to each quiz * Are there questions on the project? * I've posted a draft rubric for assessing projects. * You may find it useful to review the rubric before submitting your project. Overview: * About quiz 11 * Project stuff * The problem of sorting. * Writing sorting algorithms. * Examples: Insertion, selection, etc. * Formalizing the problem. Quiz 11 * assoc's purpose: * Search for values * What does (assoc val lst) expect as parameters? * A value * And a list * The elements of lst should be pairs * And we compare the value to the car of each of those pairs, in turn Write (acronym list-of-strings) * Grab the first character from each string * Join them all together into a string (define acronym (lambda (strings) (list->string (map (r-s string-ref 0) strings)))) Project: * Can we write helper procedures, as long as we document them? * Yes * Is it okay if it has an expected width-to-height ratio and looks less good with different width-to-height ratios? * Yes, provided it does scale horizontally and vertically Main topic today: Sorting * Given a collection of values * Put them in order, typically from smallest to largest Why do this? * Permits us to use binary search on the result * Might be useful for compressing * An inefficient way to find the largest or smallest thing * People like organized lists - "It's nicer when the data are sorted" Two other things to think about * Formalize the problem: What does it mean to sort, what are the inputs, what are the preconditions, etc? * Write the algorithm Sorting Algorithm 1 * Step through the positions, starting at postition 1 * Move that person to the left until you find someone smaller than them (or at the left of the list)