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