CSC151.02 2016S, Class 51: Insertion Sort ========================================= _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Some preparation. * Lab. Preliminaries ------------- ### Admin * New partners. * I will continue to bring you food (or food-like substances) until I am caught up on grading. * Today: Cookies. * Sunday is Mother's day. If you are fortunate enough to have a mother or mother equivalent who is important to you, make sure to let that person know. * SGA will help with their cool "send your mom a card" event on Thursday. JRC Lobby. ### Reminders * Office hours this week * See . * 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 someone, we hope * Thursday at 10 am with SamR (I'll be a few minutes late) * Thursday at 8pm in CS commons with Alex ### Upcoming Work: * Quiz Friday * Association lists * Binary search * Sorting concepts * Reading for Friday [Merge Sort](../readings/merge-sort-reading.html) * Lab Writeup: 2e, 3 * Send email titled __CSC 151 Lab Writeup 51 (Your Names)__ * Do not include the underscores. * Send to * Due before class on Monday. * [Exam 4](../assignments/exam.04.html) due next Tuesday * Prologue due Friday night * Epilogue also due next Tuesday. ### 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 * Town Hall Thursday, Unpopular Identities. 11 a.m. and some other time. * 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. Food served. #### Peer * Flute Ensemble, Thursday, 7:30, Bucksbaum Gallery. * Rushdie's East/West, May 6/7 at 7:30 p.m. No tickets necessary. * May 14 long-form and short-form improv workshop and then performance. * Humans of Grinnell College on Facebook. * KPop Gardner. Friday the 6th .... More details on Friday. #### 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 (NOT THIS WEEK) * Effective Altruism club, 2:30-3:30 Sundays in JRC 226. #### Misc ### Questions Preparation: A Few Questions on Insertion Sort ---------------------------------------------- Did we talk about this sorting algorithm yesterday? > Nothing quite like this. What is the key idea in insertion sort? > Two groups of items - Those that are alreay sorted (in order) > Then insert items from unsorted group into the correct place in the sorted group. Problem: How do you put them in between? > See the `insert-number` algirthm. How does insertion sort differ in lists and vectors? > For lists, we have two separate lists and keep building a new sorted list each time. > For vectors, we do it in place and keep track of an "imaginary boundary" > The imaginary boundary is an index in the vector that separates the portion that we know is sorted from the portion that we know is unsorted. > We have to "shift right" to put a new element in. Why do we provide you with three different kinds of list-based insertion sort (and four kinds of insertion sort)? > One handled only numbers. > One of them uses a predicate, so it could deal with any type. > There was a third one that used a "get key" to tell what were sorting by. Why would we use a "get-key"? (define list-keyed-insertion-sort (lambda (lst get-key may-precede?) > Example: We are sorting students. `(LNAME FNAME FAVECOLOR BOX HOMELOG HOMELAT)` > When sorting, we might say "We're sorting by box number". `get-key` is then `(r-s list-ref 3)`. `may-precede?` is `<=`. Lab --- * Do [the lab on insertion sort](../Labs/insertion-sort-lab.html). * Be prepared to reflect. * Writeup 51: 2e, 3