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