CSC151, Class 48: Sorting Lab

Overview:
* Question from last class:
  How do you split an arbitrary list into "large" and
    "small" elements?
* Six P's of Sorting
* Lab

Notes:
* Food: Dried fruit and chocolate
* Planning for Monday: 
  + Invite guests
  + Format: 2 min setup; 4 min demo; 4 min "hardest part";
    2 min Q&A
* More sorting next week on Tuesday

----------------------------------------

Informal notion of what sort does

;;; Procedure:
;;;   amanda-sort
;;; Parameters:
;;;   smaller?, a binary procedure used to order the
;;;     elements
;;;   lst, a list to sort
;;; Purpose:
;;;   sorts lst
;;; Produces:
;;;   sorted, a list
;;; Preconditions:
;;;   lst is finite
;;;   lst should be homogeneous (all the same kind of
;;;      things, such as all numbers, all strings, all ...)
;;;   smaller? should be applicable to the elements of lst.
;;;   smaller? should be transitive.  That is,
;;;     (smaller? a b) and (smaller? b c) implies
;;;       (smaller a c)
;;;   lst contains no equal elements
;;; Postconditions:
;;;   sorted is sorted.
;;;   each element of sorted is smaller than the subsequent
;;;     element.  In Scheme 
;;;       (smaller? (list-ref sorted i)
;;;                 (list-ref sorted (+ i 1)))
;;;   for all reasonable i (for mathematicians, i ranges
;;;     from 0 to length-2)
;;;   sorted contains the same elements as lst, but possibly
;;;     in a different order.  sorted and lst are permutations.
;;; Practica:
;;;   To sort a list of numbers in increasing order
;;;   > (amanda-sort < numbers)
;;;   To sort a list of numbers in decreasing order
;;;   > (amanda-sort > numbers)
;;;   To sort a list of strings in increasing order
;;;   > (amanda-sort string<? strings)
----------------------------------------

Given an arbitrary list of values and a smaller? comparator, 
how can we split them into "small things" and "large things"?

This problem puzzled computer scientists for many years.

A wise computer scientist whose name I forget said the same
thing as AC and AC: "Pick a random element and cross your
fingers"

This last sorting algorithm is called "Quicksort"