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