CSC151.01 2014F, Class 49: Insertion Sort
=========================================

* New partners!
* Random numbers for the exam distributed.

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Exam Questions.
    * Other Questions.
* Preparation.
* Lab.

Preliminaries
-------------

### Admin

* Welcome back!  I hope you had a relaxing break.
* Tomorrow we will look at your project images.
* Wednesday we will look at your project code.

### Upcoming Work

* Exam 4 due **Monday**, December 8.
    * Due Monday because I need time to grade before Friday.
    * Printed copy due Tuesday
    * Prologue due this Friday.
* Lab writeup: Problems 2e and 4f: <http://bit.ly/151-2014F-w49>
* No reading for Tuesday (or Wednesday).

### Extra Credit Opportunities

#### Academic

* CS 207 presentations Wednesday at 11:00 a.m.: Sports Scheduling
* CS Extras Thursday the 4th: Summer Opportunities in CS

#### Peer Support

* Karan's radio show 11pm Thursday nights on KDIC 
* Evan's radio show 5pm Friday nights on KDIC
* Donna's radio show Sunday midnight on KDIC
* Noteworthy at the Dance performance (Once Upon a Time, Splintered), 
  December 4 and 5 in Flanagan
* One acts, December 5 and 6 in Roberts
* Pioneer Swim Meet, December 5 and 6 in the Osgood

### Questions on the Exam

### Other Questions

Preparation
-----------

Four minutes with your partner ...

* What is the key idea in insertion sort?
* How does insertion sort differ in lists and vectors?
* Why do we provide you with three different kinds of list-based insertion
  sort (and four kinds of insertion sort)?
    * `(numbers-insertion-sort numbers)`
    * `(list-insertion-sort lst may-precede?)`
    * `(list-keyed-insertion-sort lst get-key may-precede?)`
    * `(vector-insertion-sort! vec may-precede?)`
* What murkiness remains?

Key Idea

* There are ways to sort lists and vectors.
* There is not one right way to sort.
    * But some are faster.
* Insertion sort (and many sorts) sorts by comparing elements
* Base idea: Inserting into lists (or subarrays)
    * Conceptually separate elements into two parts
        * Things that we know are in order
        * Things we haven't looked at yet
        * Repeatedly grab a thing from the second sequence and insert
          it into the right place in the first sequence

Sorting Vectors vs. Sorting Lists

* To sort lists, you have to build new lists.
* To sort vectors, you have to rearrange the vector
    * That means you need to keep track of an implicit "boundary" between
      the part of the vector that is sorted and the part that is not
      sorted.  (In the example, sorted things are to the left.)

Murkiness

Lab
---

* If you have not done so already, do Check 2.  (You should have done so
  already, but I realize that it was break.)
* In writing `insert-string`, you may find it useful to look at
  `insert-number`.