;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Insertion Sort ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; iSort: list-of-numbers --> list-of-numbers ;; Return a list with all elements of nums, in ascending order. ;; Uses an insertion-sort. ;; (define (iSort nums) (cond [(empty? nums) empty] [(cons? nums) (insert (first nums) (iSort (rest nums)))])) ;; insert: number, list-of-numbers --> list-of-numbers ;; Return an ascending list with the elements of already-sorted ;; and also new, inserted into the correct (ascending) place. ;; ;; Pre-condition: Already-sorted must be in ascending order. ;; (define (insert new already-sorted) (cond [(empty? already-sorted) (list new)] [(cons? already-sorted) (cond [(< new (first already-sorted)) (cons new already-sorted)] [else (cons (first already-sorted) (insert new (rest already-sorted)))])])) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Selection Sort (2-pass) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; sSort2: list-of-numbers --> list-of-numbers ;; Return a list with all elements of nums, in ascending order. ;; Uses a selection sort (2-pass). ;; (define (sSort2 nums) (cond [(empty? nums) empty] [(cons? nums) (local {(define m (find-min nums))} (cons m (sSort2 (remove m nums))))])) ;; remove: x, cons-of-x --> list-of-x ;; Return the elements of lst, but missing (at most) one copy ;; of target. ;; Precondition: target must occur in lst. ;; (define (remove target lst) (cond [(empty? lst) (error 'remove "~v not found." target)] [(cons? lst) (cond [(= (first lst) target) (rest lst)] [else (cons (first lst) (remove target (rest lst)))])])) ;; find-min: cons-of-number --> number ;; Return the smallest element of lst. ;; (define (find-min lst) (cond [(length=1? lst) (first lst)] [else (local {(define minrest (find-min (rest lst)))} (cond [(< minrest (first lst)) minrest] [else (first lst)]))])) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Selection Sort (fancy 1-pass version) ;;;;;;;;;;;;;;;;;;;;;;;;; ;; sSort1: list-of-numbers --> list-of-numbers ;; Return a list with all elements of nums, in ascending order. ;; Uses a selection sort (1-pass -- essentially bubblesort). ;; (define (sSort1 nums) (cond [(empty? nums) empty] [(cons? nums) (local {(define select-min (min/rest nums))} (cons (first select-min) (sSort1 (second select-min))))])) ;; min/rest: list-of-numbers --> (list number list-of-number) ;; Return the num's min, and everything but num's min. ;; A helper for sSort1. ;; (define (min/rest nums) (cond [(length=1? nums) (list (first nums) empty)] [(cons? nums) (local {(define min-and-others (min/rest (rest nums))) (define min (first min-and-others)) (define others (second min-and-others))} (cond [(< (first nums) min) (list (first nums) (cons min others))] [else (list min (cons (first nums) others))]))])) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Merge Sort ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; mSort: list-of-number --> list-of-number ;; Return a list with the same elements of lon, in ascending order. ;; (define (mSort lon) (cond [(length<=1? lon) lon] [else (local {(define two-parts (unzip lon)) (define one-part (first two-parts)) (define other-part (second two-parts))} (merge-two (mSort one-part) (mSort other-part)))])) ;; (merge-two l1 l2) ;; l1, l2 are ascending lists of numbers ;; return a single ascending list of the numbers of of l1,l2. ;; ;; Example: ;; (merge-two (list 3 8 11) (list 1 3 4 9 29)) ;; = (list 1 3 3 4 8 9 11 29) ;; (define (merge-two l1 l2) (cond [(and (empty? l1) (empty? l2)) empty] [(and (empty? l1) (cons? l2)) l2] [(and (cons? l1) (empty? l2)) l1] [(and (cons? l1) (cons? l2)) (cond [(> (first l1) (first l2)) (cons (first l2) (merge-two l1 (rest l2)))] [else (cons (first l1) (merge-two (rest l1) l2))])])) ;; unzip: list-of-x --> (list list-of-x list-of-x)) ;; Return two lists, each containing every-other element of lst ;; (in unspecified order). ;; (define (unzip lst) (unzip-help lst empty empty)) ;; unzip-help: list-of-x list-of-x list-of-x --> (list list-of-x list-of-x) ;; Return two lists, each containing every-other element of lst ;; and the elements of so-far1 (so-far2) respectively. ;; (define (unzip-help lst so-far1 so-far2) (cond [(empty? lst) (list so-far1 so-far2)] [(cons? lst) (unzip-help (rest lst) so-far2 (cons (first lst) so-far1))])) ; Fancy footwork: swap order of so-far1, so-far2. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; QuickSort ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; qSort: list-of-numbers --> list-of-numbers ;; Return a list with all elements of nums, in ascending order. ;; (define (qSort nums) (cond [(empty? nums) empty] [else (local [(define pivot (first nums))] (append (qSort (filter (lambda (n) (< n pivot)) nums)) (filter (lambda (n) (= n pivot)) nums) ; DON'T recur here! (qSort (filter (lambda (n) (> n pivot)) nums))))])) ;;;;;;;; General-purpose helpers. ;; length<=1?: list --> boolean ;; length=1?: list --> boolean ;; (define (length<=1? lst) (or (empty? lst) (empty? (rest lst)))) (define (length=1? lst) (and (cons? lst) (empty? (rest lst)))) ;; positive?: real --> boolean ;; Is the n > 0? ;; (define (positive? n) (> n 0)) (define max-rand 32768) ; A constant (used in generating random lists) ;;;;;;;;; Generating test lists. ;; nums-up: natnum --> list-of-num ;; nums-down: natnum --> list-of-num ;; nums-rand: natnum --> list-of-num ;; ;; Return a list of n descending, ascending, or random numbers. ;; (Random natnums in [0,max-rand).) ;; (define (nums-down n) (cond [(zero? n) empty] [(positive? n) (cons n (nums-down (sub1 n)))])) (define (nums-up n) (reverse (nums-down n))) (define (nums-rand n) (cond [(zero? n) empty] [(positive? n) (cons (random max-rand) (nums-rand (sub1 n)))])) ;;;;; ;(mSort (nums-rand 20)) ;(iSort (nums-rand 20)) ;(qSort (nums-rand 20)) ;(sSort2 (nums-rand 20)) ;(sSort1 (nums-rand 20))