CS200: Computer Science, Spring 2004

Notes: Wednesday 3 March 2004
Schedule
 Friday, 5 March: Problem Set 5 (note: you have 2 extra days for PS5 from the original course schedule)
 Before 15 March: Read the rest of GEB Part I (see Notes 5)
Insert Sort in Halves (define (sublist lst start end) (if (= start 0) (if (= end 0) null (cons (car lst) (sublist (cdr lst) start ( end 1)))) (sublist (cdr lst) ( start 1) ( end 1)))) (define (firsthalf lst) (sublist lst 0 (floor (/ (+ 1 (length lst)) 2)))) (define (secondhalf lst) (sublist lst (floor (/ (+ 1 (length lst)) 2)) (length lst))) (define (insertelh cf el lst) (if (null? lst) (list el) (let ((fh (firsthalf lst)) (sh (secondhalf lst))) (if (cf el (car fh)) (append (cons el fh) sh) (if (null? sh) (append fh (list el)) (if (cf el (car sh)) (append (insertelh cf el fh) sh) (append fh (insertelh cf el sh)))))))) (define (insertsorth cf lst) (if (null? lst) null (insertelh cf (car lst) (insertsorth cf (cdr lst)))))Insert Sort using Trees (define (maketree left el right) (list left el right)) (define (getleft tree) (first tree)) (define (getelement tree) (second tree)) (define (getright tree) (third tree)) (define (inserteltree cf el tree) (if (null? tree) (maketree null el null) (if (cf el (getelement tree)) (maketree (inserteltree cf el (getleft tree)) (getelement tree) (getright tree)) (maketree (getleft tree) (getelement tree) (inserteltree cf el (getright tree)))))) (define (extractelements tree) (if (null? tree) null (append (extractelements (getleft tree)) (cons (getelement tree) (extractelements (getright tree)))))) (define (insertsorttree cf lst) (define (insertsortworker cf lst) (if (null? lst) null (inserteltree cf (car lst) (insertsortworker cf (cdr lst))))) (extractelements (insertsortworker cf lst)))Quick Sort (define (quicksort cf lst) (if (null? lst) null (append (quicksort cf (filter (lambda (el) (cf el (car lst))) (cdr lst))) (list (car lst)) (quicksort cf (filter (lambda (el) (not (cf el (car lst)))) (cdr lst))))))Measuring Orders of Growth Here is the code I used for measuring orders of growth. It uses some MzScheme extensions that are not part of standard Scheme to time how long evaluations take.(define (timesort sortproc len) (let ((vals (randintlist len))) (letvalues ([(val utime ptime gctime) (timeapply sortproc (list < vals))]) utime))) (define (findratios lst) (if (< (length lst) 2) null (let ((thisone (first lst)) (nextone (second lst))) (cons (exact>inexact (/ (cdr nextone) (cdr thisone))) (findratios (cdr lst)))))) (define (testgrowth sortproc) (let ((sizes (list 250 500 1000 2000 4000 8000 16000 32000 64000 128000))) (findratios (map (lambda (len) (let ((time (timesort sortproc len))) (printf "n = ~a, time = ~a~n" len time) (cons len time))) sizes))))History Sir Tony Hoare developed the QuickSort algorithm in 1960. His first assignment at a job with a small computer manufacturer was to implement a sorting routing based on the best thenknown algorithm (Shell Sort, which is a Θ(n^{2}) algorithm that is a slight improvement on the InsertSort alrogithm we saw in class). He thought he could do better, and his boss bet him sixpence that he couldn't. Quicksort was the algorithm that resulted. Since it is Θ(n log n) it is clearly better than Shell Sort theoretically (that is, it is always eventually faster once n is large enough), and is also better than Shell Sort in practice for nearly all applications.Hoare received the 1980 Turing Award (the highest award given in Computer Science, it is named for Alan Turing, one of the codebreakers who worked at Bletchley Park during WWII. We will learn about Turing's contributions to Computer Science after Spring Break) for contributions to the design of programming languages. His award speech, The Emperor's Old Clothes, presents principles from his experiences designing programming languages. One of his claims is,
I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.CS200 students would be wise to follow this advice in all your programs!
cs200staff@cs.virginia.edu Using these Materials 