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?