CSC151 2009F, Class 46: Introduction to Sorting

Admin:
* Reading for Tuesday: Sorting, 
  * Revisits the topics of today's class in more detail.
* Quiz 11 returned
  * Depressing: 
    * (a) Many forgot what assoc does
    * (b) Even though acronym was on the lab, many solutions were wrong
    * (c) We screwed up the order of parameters to assoc
  * Because of (c), I've added 2 to each quiz
* Are there questions on the project?
* I've posted a draft rubric for assessing projects.  
  * You may find it useful to review the rubric before submitting 
    your project.

Overview:
* About quiz 11
* Project stuff
* The problem of sorting.
* Writing sorting algorithms.
* Examples: Insertion, selection, etc.
* Formalizing the problem.

Quiz 11
* assoc's purpose:
  * Search for values
* What does (assoc val lst) expect as parameters?
  * A value
  * And a list
* The elements of lst should be pairs
* And we compare the value to the car of each of those pairs, in turn

Write (acronym list-of-strings)
* Grab the first character from each string
* Join them all together into a string

(define acronym
  (lambda (strings)
      (list->string (map (r-s string-ref 0)
                             strings))))

Project:
* Can we write helper procedures, as long as we document them?
  * Yes
* Is it okay if it has an expected width-to-height ratio and looks
  less good with different width-to-height ratios?
  * Yes, provided it does scale horizontally and vertically

Main topic today: Sorting
* Given a collection of values
* Put them in order, typically from smallest to largest

Why do this?
* Permits us to use binary search on the result
* Might be useful for compressing
* An inefficient way to find the largest or smallest thing
* People like organized lists - "It's nicer when the data are sorted"

Two other things to think about
* Formalize the problem: What does it mean to sort, what are the inputs, 
  what are the preconditions, etc?
* Write the algorithm 

Sorting Algorithm 1
* Step through the positions, starting at postition 1
  * Move that person to the left until you find someone smaller than
    them (or at the left of the list)