CSC151.02 2003F, Class 46: Insertion Sort
Admin
* Read "Merge Sort" for Monday.
* Finish the "guess a number" game before Wednesday at 5pm.
* The picture was me.
* Yesterday's class.
* Visual
* First-hand view
* No computers
* Exercise
Overview:
* Review of yesterday's class.
* Q and A.
* Lab
* Reflections
What did we learn yesterday?
* Lots of kinds of sorting
* Quicksort: Split into small and big stuff, sort each half, join together
* Merge sort: Split in half, sort each half, merge together using a more complex process
* Insertion sort (in reading): Repeatedly insert things into the "correct" place in a sorted list.
* Selection sort: Repeatedly select the smallest remaining element
* Why to sort
* Support searching
* Support characterizing the top 10% or something similar
* Nothing better to do
* Relative efficiency and approximate formulae
* Relearned the term "transitive"
* Six P's of sorting
* Parameters:
* lst, a list
* may-precede?, a binary comparator
* Produces:
* sorted, a list
* Preconditions:
* The comparison operation must be applicable to any two things in the list
* may-precede? must be transitive
* Postconditions:
* The result list is a permutation of the original list (or "nothing has been added, nothing has been deleted, it's all just rearranged")
* sorted is in order, each element is no bigger than the next element, in Scheme (may-precede? (list-ref lst i) (list-ref lst (+ i 1))) for all reasonable i.
What did you learn from the reading? Or what questions do you have?
* What does revappend do?
Do the lab!