CSC151.02 2016S, Class 50: An Introduction to Sorting ===================================================== _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * The problem of sorting. * Writing sorting algorithms. * Examples: Insertion, selection, etc. * Formalizing the problem. Preliminaries ------------- ### Admin * Continue partners. * I will continue to bring you food (or food-like substances) until I am caught up on grading. * Today: Candy ### Reminders * Office hours this week * See http://rebelsky.youcanbook.me. * Ask me about other available times. * Tutor hours * Sunday, 3-5 p.m. * Sunday-Thursday, 7-10 p.m. * Review Sessions * Wednesday at 8pm in CS commons with Evan * Thursday at 10 am with SamR * Thursday at 8pm in CS commons with Alex ### Upcoming Work: * Reading for Wednesday: [Sorting](../readings/sorting-reading.html) * Projects due TONIGHT. * Exam 4 distributed (as draft). Due next Tuesday. * Official distribution of exam 4 tomorrow. ### Extra Credit * Send your reports to with subject "CSC 151 Extra Credit". (Do not include the quotation marks.) * Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!" #### Academic / Artistic * Thursday's CS Extra on STEM for the Blind. 4:15 p.m. in Science 3821. Food in the commons beforehand. * Thursday, May 5, 8pm, the Science of Substances. * Finals week's *Inside Grinnell*. Tuesday, May 17 at noon in JRC 101. The College Budget. Food served. * Town Hall Thursday, Unpopular Identities. 11 a.m. and some other time. #### Peer * Flute Ensemble, Thursday, 7:30, Bucksbaum Gallery. * Rushdie's East/West, May 6/7 at 7:30 p.m. No tickets necessary. * Humans of Grinnell College on Facebook. #### Regular Peer * Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio * Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203. Just show up; you don't need to sign up. * Pun club Saturdays at 4pm in Younker * Electronic Potpourri on KDIC Fridays at Five * Space Odyssey KDIC Fridays at Six * Bollywood, Fridays, 7:30-8:30, Younker * Effective Altruism club, 2:30-3:30 Sundays in JRC 226. #### Misc ### Questions _Will the representative values be in the names of the images?_ > Yes, _I can't create the tar/zip file. What do I do?_ > Just attach all of the files to the message. _How much documentation for the helpers?_ > 4Ps would be nice. _What if I've written 26 nearly-identical procedures?_ > You can write `;;; "See above"` _If it's not important what the procedure returns, because, say, we've called a GIMP procedure, what should we do?_ ;;; Produces: ;;; [Nothing of import] _How should we deal with the images we are copying and pasting?_ > Put them in a folder on your desktop. Email me the name of that folder and a note that "Sam, I give you permission to make that folder accessible." I'll fix things. _Do we have to document internal helper procedures from a named `let` or `letrec` or whatever?_ > No, but one line is often nice. _Document?_ > Yes. In ways that you think are clear. The problem of sorting ---------------------- Given a collection of values, put them in order. * Order students by last name. * Order movies by average rotten tomatoes rating. * Dance moves by complexity. * Books by title. * Titular head movies by number of groans they elicit. As computer scientists, we want to think about * How we formally specify what it means to "sort" or "order" a collection? * Six-P's (or at least the first four) * How do write a good sorting algorithm? * How do we decide whether one sorting algorithm is better than another? * How are we confident that our sorting algorithm is correct? Designing a sorting algorithm ----------------------------- Think about writing a `sort` procedure in Scheme. What inputs would you have? What outputs would you have? ### Group 1 * Input 1: The list to sort. * Input 2: A binary comparator that lets us determine the order of two values. * Output: A list ### Group 2 * Input 1: The vector to sort. * Input 2: A binary comparator that lets us determine the order of * Output: None; we've changed the vector in place ### Notes * Comparator is important. * We will look at vectors. Writing sorting algorithms -------------------------- We are going to sort 8 of you alphabetically by name. We already know how to compare things alphabetically. How do we get these eight people in order? ### Strategy 1: TCNC Sort (aka Bubble Sort) * Compare elements at positions 1 and 2. Swap if out of order. * Compare elements at positions 2 and 3. Swap if out of order. * ... * Compare elements at positions N and N-1. Swap if out of order. * Do it all over again * And again * And again * Until you don't make any swaps. #### Strategy 2: EHRB Sort * Compare elements at positions 0 and 1. If not in order, shove the larger one to the end. * Keep goiing. Will it work? It looks like it. Will it be faster? It's hard to tell. * Compare elements at position #### Strategy 3: Selection Sort * Put the smallest thing in position 0 * Put the next smallest thing in position 1 ... #### Strategy 4: TFATP Sort * Divide in half, small and large * Recurse on each half Formalizing the problem -----------------------