Slide 1Insert SortDivide and ConquerInsert Halvesappend can’t be O(1)Experimental ConfirmationComplexity of Insert Half SortMaking it fasterSlide 9Slide 10Sorted Binary TreesTree ExampleRepresenting TreesTrees as Listsinsertel-treeHow much work is insertel-tree?insertsort-treeextract-elementsComplexity of insertsort-treeSlide 20Comparing sortsCan we do better?ChargeDavid Evanshttp://www.cs.virginia.edu/evansClass 12: Quickest SortingCS150: Computer ScienceUniversity of VirginiaComputer ScienceRose Bushby Jacintha Henry & Rachel KayDandelion of Defeatby Mary Elliott Nealby Kristina Caudle2CS150 Fall 2005: Lecture 12: Quickest SortingInsert Sort(define (insertsort cf lst) (if (null? lst) null (insertel cf(car lst) (insertsort cf (cdr lst)))))(define (insertel cf el lst) (if (null? lst) (list el) (if (cf el (car lst)) (cons el lst) (cons (car lst) (insertel cf el (cdr lst))))))insertsort is (n2)3CS150 Fall 2005: Lecture 12: Quickest SortingDivide and Conquer•Both simplesort and insertsort divide the problem of sorting a list of length n into:–Sorting a list of length n-1–Doing the right thing with one element•Hence, there are always n steps–And since each step is  (n), they are  (n2) •To sort more efficiently, we need to divide the problem more evenly each step4CS150 Fall 2005: Lecture 12: Quickest SortingInsert Halves(define (insertelh cf el lst) (if (null? lst) (list el) (let ((fh (first-half lst)) (sh (second-half 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)))))Same asinsertsortexcept usesinsertelh(if (= (length lst) 1) (if (cf el (car lst)) (cons el lst) (list (car lst) el)) (let ((fh …5CS150 Fall 2005: Lecture 12: Quickest Sortingappend can’t be O(1)•Needs to make a new list of length n + m where n is the length of the first list, and m is the length of the second list•Making a list of length k requires k conses, so append must be (n + m)6CS150 Fall 2005: Lecture 12: Quickest SortingExperimental Confirmation> (testgrowthappend)n = 10000, m = 1, time = 0n = 20000, m = 1, time = 0n = 40000, m = 1, time = 0n = 80000, m = 1, time = 10n = 160000, m = 1, time = 10n = 320000, m = 1, time = 40n = 640000, m = 1, time = 70n = 1280000, m = 1, time = 150n = 2560000, m = 1, time = 290(1.0 4.0 1.75 2.14286 1.9333)n = 10000, m = 10000, time = 0n = 20000, m = 20000, time = 0n = 40000, m = 40000, time = 0n = 80000, m = 80000, time = 10n = 160000, m = 160000, time = 50n = 320000, m = 320000, time = 40n = 640000, m = 640000, time = 70n = 1280000, m = 1280000, time = 150n = 2560000, m = 2560000, time = 270(5.0 0.8 1.75 2.142857142857143 1.8)7CS150 Fall 2005: Lecture 12: Quickest Sorting Complexity of Insert Half Sort(define (insertelh cf el lst) (if (null? lst) (list el) (if (= (length lst) 1) (if (cf el (car lst)) (cons el lst) (list (car lst) el)) (let ((fh (first-half lst)) (sh (second-half lst))) (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)))))n applications of insertelhlog n applications of insertelhEach one is (n) work since append is (n)Complexity is: (n2log n)8CS150 Fall 2005: Lecture 12: Quickest SortingMaking it faster•We need to either:1. Reduce the number of applications of insertelh in insertsorth2. Reduce the number of applications of insertelh in insertelh3. Reduce the time for one application of insertelhImpossible – need to consider each elementUnlikely…each application already halves the listNeed to make first-half, second-half and append faster than (n)9CS150 Fall 2005: Lecture 12: Quickest Sorting10CS150 Fall 2005: Lecture 12: Quickest SortingThe Great Lambda Treeof Ultimate Knowledgeand Infinite Power11CS150 Fall 2005: Lecture 12: Quickest SortingSorted Binary TreeselA tree containingall elements x suchthat (cf x el) is trueA tree containingall elements x suchthat (cf x el) is falseleftright12CS150 Fall 2005: Lecture 12: Quickest SortingTree Example52 87413cf: <nullnull13CS150 Fall 2005: Lecture 12: Quickest SortingRepresenting Trees(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))left and right are trees(null is a tree)tree must be a non-null treetree must be a non-null treetree must be a non-null tree14CS150 Fall 2005: Lecture 12: Quickest SortingTrees as Lists52 81(make-tree (make-tree (make-tree null 1 null) 2 null) 5 (make-tree null 8 null))(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))15CS150 Fall 2005: Lecture 12: Quickest Sortinginsertel-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))))))If the tree is null, make a new tree with el as its element and no left orright trees.Otherwise, decideif el should be in the left or right subtree.insert it into thatsubtree, but leave theother subtree unchanged.16CS150 Fall 2005: Lecture 12: Quickest SortingHow much work is insertel-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))))))Each time we callinsertel-tree, the size ofthe tree. So, doublingthe size of the tree only increases the number ofcalls by 1!insertel-tree is  (log2 n) log2 a = bmeans 2b = a17CS150 Fall 2005: Lecture 12: Quickest Sortinginsertsort-tree(define (insertsort-worker cf lst) (if (null? lst) null (insertel-tree cf (car lst) (insertsort-worker cf (cdr lst)))))(define (insertsort cf lst) (if (null? lst) null (insertel cf (car lst)