CSC153 2004S, Class 26: "Fast" Sorting Algorithms Admin: * Cool convo today. Go. Enjoy. Think. * Questions on exam 2? * Exam 1 graded! * Problem 1: Ratio of longest/shortest: 4 * Problem 2: 4.5 * Problem 3: 5.5 * Problem 4: 10 * We'll return to continuations on Friday (our last Scheme day). * Did you hear the lastest SCO news? Overview: * Consider how to apply the "divide and conquer" technique to sorting * Key ideas in merge sort. * Key ideas in Quicksort * Lab /Notes on Exam 1/ * Don't use multi-line end-of-line comments!!!!!!!!! ; This is a procedure that does some really ; cool stuff (define my-silly-proc ; This is a procedure (lambda (whatever) ; that does some really (display "xxx") (if (test whatever whatever) ; wonderful stuff if (test) /* test for foo; * an important condition */ bar; * Work on those 6 P's, particularly the postconditions. ;;; Procedure: ;;; A DESCRIPTION OF THE PROCEDURE ;;; * Deal with it! * Document your strategies! (letrec kernel ((stuff (reverse lst)) (base 1)) (if (null? stuff) 0 (+ (* base (car stuff)) (kernel (cdr stuff) (* base 10))))) * Style (see problem 4 in exam1.scm) (if (= (length (car collection)) 3) #t #f) is the same as (= (length (car collection)) 3) Similarly (if (test1) (test2) #f) is the same as (and (test1) (test2)) Fixing code (letrec ((verify? (lambda (collection) (and (list? collection) (list? (car collection)) (= (length (car collection)) 3) (or (null? (cdr collection)) (verify? (cdr collection))))))) Running time of verify? in big-O time-verify(n) = time-listp(n) + time-listp(element) + time-length(element) + time-verify(n-1) time-verify(n) = cn + 3 + 3 + time-verify(n-1) f(n) = n + k + f(n-1) f(n) = n + k + n-1 + k + f(n-2) f(n) = n + n-1 + 2k + f(n-2) f(n) = n + n-1 + n-2 + 3k + f(n-3) f(n) = (n + n-1 + n-2 + ... n-m+1) + mk + f(n-m) When m=n f(n) = (n + n-1 + n-2 + ... 1) + nk + f(0) Assume f(0) = 0 f(n) = (n + n-1 + n-2 + ... 1) + nk f(n) = n(n+1)/2 + nk f(n) in O(n^2) Fix it by not asking whether it's a list at every step! * Consider efficiency * Remember built-in procedures string-ci