University of Virginia Computer ScienceCS150: Computer Science, Fall 2005 |
(none)19 September 2005 |

(define (make-tree left el right) (list left el right)) (define (get-left tree) (first tree)) (define (get-element tree) (second tree)) (define (get-right tree) (third tree)) (define (insertel-tree cf el tree) (if (null? tree) (make-tree null el null) (if (cf el (get-element tree)) (make-tree (insertel-tree cf el (get-left tree)) (get-element tree) (get-right tree)) (make-tree (get-left tree) (get-element tree) (insertel-tree cf el (get-right tree)))))) (define (extract-elements tree) (if (null? tree) null (append (extract-elements (get-left tree)) (cons (get-element tree) (extract-elements (get-right tree)))))) (define (insertsort-tree cf lst) (define (insertsort-worker cf lst) (if (null? lst) null (insertel-tree cf (car lst) (insertsort-worker cf (cdr lst))))) (extract-elements (insertsort-worker cf lst)))

(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))))))

(define (timesort sortproc len) (let ((vals (rand-int-list len))) (let-values ([(val utime ptime gctime) (time-apply sortproc (list < vals))]) utime))) (define (find-ratios lst) (if (< (length lst) 2) null (let ((thisone (first lst)) (nextone (second lst))) (cons (exact->inexact (/ (cdr nextone) (cdr thisone))) (find-ratios (cdr lst)))))) (define (testgrowth sortproc) (let ((sizes (list 250 500 1000 2000 4000 8000 16000 32000 64000 128000))) (find-ratios (map (lambda (len) (let ((time (timesort sortproc len))) (printf "n = ~a, time = ~a~n" len time) (cons len time))) sizes))))

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 then-known 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,

CS150 students would be wise to follow this advice in all your programs!I conclude that there are two ways of constructing a software design: One way is to make it so simple that there areobviouslyno deficiencies and the other way is to make it so complicated that there are noobviousdeficiencies.

CS 150: Computer ScienceUniversity of Virginia |
evans@cs.virginia.eduUsing these Materials |