CSC151.01 2014F, Class 48: An Introduction to Sorting
=====================================================

* Sit with whomever you'd like.

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* The problem of sorting.
* Writing sorting algorithms.
* Examples: Insertion, selection, etc.
* Formalizing the problem.

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

### Admin

* Have an terrific Thanksgiving.  I hope that you have much to be thankful
  for.  And please take care to be safe.
* No review sessions this week.
* We are doing algorithm design today.  
    * You learn algorithm design better by trying than by reading/listening. 
    * You learn better if you design the algorithm before thinking about
      how to express it in a programming language.
    * So today is an "away from computer" day.

### Upcoming Work

* Exam 4 due MONDAY, December 8.
* No lab writeup.
* Reading for Monday:
  [Sorting](../readings/sorting.html)

### Extra Credit Opportunities

#### Academic

* CS Extras Thursday the 4th: Summer Opportunities in CS

#### Peer Support

* Karan's radio show 11pm Thursday nights on KDIC (not this week)
* Evan's radio show 5pm Friday nights on KDIC  (not this week)
* 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

### Questions

Review: Binary Search
---------------------

* Given a list that's organized (e.g., alphabetically by name,
  numerically by Dewey Decimal number) look in the middle and
  figure out what half your element is on.  Then run the element
  again on that half.
* Slight corrections to the above:
    * In the most general version, we need a way to determine how
      it's organized.
    * If we see the element when we look in the middle, STOP!
    * If you run out of elements, issue an error (either -1 or #f 
      or an error)
    * (Until corrected, we had "do it again and again" rather than
      a clear recursive approach.)
    * Clarification: What if the list can't be split in half (or has
      no "middle"?  Answer: Look next to the half (round down)  E.g.,
      if there are 16 things, we treat the eighth thing (position 7)
      as the middle.
    * This only works on vectors.  It's a PITN to look for the middle
      element of a list.
* Note: We do not have anything more efficient for lists than looking
  at them one at a time.

The problem of sorting
----------------------

* Given an unorganized vector, and an organizing principle, organize it
* List of names, put them in alphabetical order.

Writing sorting algorithms
--------------------------

* Design one (or two)!

Examples: Insertion, selection, etc
-----------------------------------

* Insertion sort
* Bubble sort
* Parallel bubble sort
* Selection sort

Formalizing the problem
-----------------------

*Not down.*