CSC151 2009F, Class 47: Insertion Sort Admin: * Reading for tomorrow: Merge Sort. * Projects have started to arrive. Yay! * In a number of cases, I've suggested that folks review the grading rubric for the project. * (Don't lose those easy points, folks!) * We'll strive for ten minutes of lecture/discussion followed by lots of lab time. * EC for * Watching some unnamed track coaching Grinnell alum on Jeopardy at 3:30 today * Womens basketball (looking ahead) Overview: * What is the key idea of insertion sort? * Why do we have multiple versions of insertion sort? * Lab Sorting: Goal is to put a collection in order * We have different representations of collections: * vectors * lists * We think about sorting lsits and sorting vectors differently * lists are immutable, so when we sort a list, we build a new list * vectors are mutable, so we often sort "in place" * Yesterday: Different techniques for sorting, often with a key idea * First technique: Shift elements until they seem to be in the "right" position "Shifty sort" * Second technique: Select the smallest remaining element and put it at the front * Today: Another technique: Insertion sort, starting with lists * Repeatedly insert elements into an expanding sorted list * Reading gave four versions of insertion sort * numbers-insertion-sort * Easier to understand * list-insertion-sort * A straightforward generalization * list-keyed-insertion-sort * Working with a list of lists, and we want to sort by one part of the compound values * E.g., a list of (name/phone-number/fave color) triples, and we want to sort by phone number * vector-insertion-sort! * Everything else works on lists, we need at least one thing to sort vectors