CSC151, Class 47: Sorting

Overview:
* Quick note on searching
* The problem of sorting
* Examples
* Expressing sorting algorithms in Scheme

Notes:
* Read the reading on sorting.
* See the whiteboard behind this screen
* Math/CS Picnic: 
  Be there and be square
* Did you finish the lab?  Why not?
* YGB Concert Saturday at 2pm in Sebring-Lewis
* Student composers concert next Wednesday, same place,
  7:30 p.m. more extra credit!
* Reminder: Reese can answer questions, too.

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

First problem: Determine if a list of characters contains
the character #\a using sequential-search-list

(sequential-search-list pred? lst)

(define fred (list #\f #\r #\e #\d))

(define letter-a?
  (lambda (ch) (equal? #\a ch)))

(sequential-search-list letter-a? fred)

(sequential-search-list letter-a? (list #\f #\r #\e #\d))

(sequential-search-list (lambda (ch) (equal? #\a ch))
                        (list #\f #\r #\e #\d))

The ability to create procedures without naming them is one
of the great powers of Scheme.

Mr. Stone uses this ability a lot of the time.

We can also write procedures that create procedures.

;;; Procedure:
;;;   left-section
;;; Parameters:
;;;   proc, a procedure of two parameters
;;;   val, a value
;;; Purpose:
;;;   Fill in the first of the two paraemters to
;;;     proc.
;;; Produces:
;;;   newproc, a unary procedure.
;;; Postconditions:
;;;;  (newproc x) is the same as (proc val x)
;;; Practica:
;;;   (left-section + 5) -> gives you a procedure that
;;;     adds five to its argument
;;;   (left-section = 2) -> gives you a procedure that
;;;     test if its argument is 2.
(define left-section
  (lambda (proc val)
    (let ((newproc (lambda (x) (proc val x))))
       newproc)))

(define left-section
  (lambda (proc val)
    (lambda (x) (proc val x))))

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

Computer scientist look for common problems, generalize,
solve (with algorithms), and analyze their solution

Amanda Sort (Insertion Sort)
  Make two lists, unsorted and sorted
  unsorted initially contains all but one element of the
    original list
  sorted initially contains one element
  repeatly take an element from unsorted and put it in
   the right place in sorted

  To put something in the right place in a sorted list:
    Look at each element in turn until you find a larger
      element or reach the end of the list.  Put the
      element there.
    If the "list" were big enough, we could use binary
      search to find the right place.
  sort

Andy/Kirsten Sort (merge sort)
  Divide into two (or five or ...) piles
  Sort each pile using Andddddy/Kirsten sort
  Merge each pile using the technique of
    compare top elements and use smallest

Which algorithm is better (if we were implementing in Scheme)?
* Second one seems to redo work a lot
* Nya Nya: The first one redoes a lot of work, too.
* Note: Binary search won't work well int he first one;
  we either can't use it (our data are in a list) or it's
  hard to shove something in the middle (our data are in a
  vector).
* Merge sort is "pretty"
* Merge sort is faster for big lists (or so we think).
* Insertion sort is probably faster for small lists.
* Merge sort requires deep recursion.  SOme folks whose plans
  I read hate deep recursion.

We look at issues other than speed:
* Which one can I implement correctly?
* Which one can I modify easily?
* ...

Sam Sort (also known as Selection Sort or "Eeuhg Sort")
* Repeatedly take the smallest element and put add it to
  the end of your sorted list.
* Speeds up at the end (vs. Amanda sort which slows down at
  the end)

Yvonne Sort 
* Split the list into categories A-M, N-Z
* Sort each category (recursively)
* Join them together easily

How do you split into "smaller things" and "larger things"
if you don't know much about the data?