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?