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