;; INSERTION SORT ;; numsort : [Listof Number] -> [Listof Number] ;; sort lon in ascending order (define (numsort lon) (cond [(empty? lon) empty] [(cons? lon) (insert (first lon) (numsort (rest lon)))])) (check-expect (numsort '()) '()) (check-expect (numsort '(3 2 1)) '(1 2 3)) (check-expect (numsort '(7 5 8 -14 7 13)) '(-14 5 7 7 8 13)) ;; ------ ;; insert : Number [Listof Number] -> [Listof Number] ;; Assume lon is sorted in ascending order ;; insert n into lon at the appropriate position, producing sorted list (define (insert n lon) (cond [(empty? lon) (list n)] [(cons? lon) (cond [(<= n (first lon)) (cons n lon)] [else (cons (first lon) (insert n (rest lon)))])])) (check-expect (insert 4 '()) '(4)) (check-expect (insert 4 '(1 2 8)) '(1 2 4 8)) (check-expect (insert -4 '(1 2 8)) '(-4 1 2 8)) (check-expect (insert 7 '(-14 5 7 8 13)) '(-14 5 7 7 8 13)) ;-------------------------------------------------------------- ;; QUICKSORT [developed by C.A.R. Hoare (Tony Hoare), 1961] ;; NOTE: Following version is incorrect; it does not terminate! ;; numsortq : [Listof Number] -> [Listof Number] ;; sort lon in ascending order ;; IDEA: pick pivot (first elt in lon); divide into less-equals than pivot ;; and greater than pivot; recur; append results #;(define (numsortq lon) (cond [(empty? lon) empty] [else (local ((define pivot (first lon)) (define less-equals (filter (lambda (x) (<= x pivot)) lon)) (define greaters (filter (lambda (x) (> x pivot)) lon))) (append (numsortq less-equals) (numsortq greaters)))])) ;; ---------------------------- ;; Following version terminates ;; numsortq : [Listof Number] -> [Listof Number] ;; sort lon in ascending order ;; HOW: ;; - pick pivot (first elt in lon); ;; - divide into 3 lists: lesser than pivot, equal to pivot, ;; and greater than pivot; ;; - recur on lessers and greaters; ;; - append results ;; TERMINATES: because we recur on lessers and greaters, ;; where both are smaller lists than lon (with at least pivot removed) (define (numsortq lon) (cond [(empty? lon) empty] [(empty? (rest lon)) lon] ;; single element list -- can treat as a special case, but not essential ; -- complex case [else (local ((define pivot (first lon)) (define lessers (filter (lambda (n) (< n pivot)) lon)) (define sames (filter (lambda (n) (= n pivot)) lon)) (define greaters (filter (lambda (n) (> n pivot)) lon))) (append (numsortq lessers) sames (numsortq greaters)))])) (check-expect (numsortq '()) '()) (check-expect (numsortq '(3 2 1)) '(1 2 3)) (check-expect (numsortq '(7 5 8 -14 7 13)) '(-14 5 7 7 8 13))