;; [List-of Number] -> [List-of Number] ;; WHAT: sort the given list of numbers in ascending order ;; HOW : determine pivot, sort those numbers smaller and larger ;; than pivot separately, append results with pivot in middle ;; TERMINATES for all possible input lists because ;; the recursive calls are guaranteed to receive smaller lists ;; than the given l (check-expect (quick-sort '(3 1 2 4 0)) '(0 1 2 3 4)) (check-expect (quick-sort '(2 1 3 4 0)) '(0 1 2 3 4)) (define (quick-sort l) (cond ;; ------------------------------------------------------- ;; trivial problems: [(empty? l) l] [(one? l) l] [(two? l) (list (apply min l) (apply max l))] ;; ------------------------------------------------------- [(cons? l) (local (;; ---------------------------------------------- ;; splitting the problem (define pivot (first l)) (define equals* (filter (lambda (n) (= n pivot)) l)) (define smalls* (filter (lambda (n) (< n pivot)) l)) (define large* (filter (lambda (n) (> n pivot)) l)) ;; ---------------------------------------------- ;; recursively solve (define small-sorted (quick-sort smalls*)) (define large-sorted (quick-sort large*))) ;; ---------------------------------------------------- ;; combine solutions: (append small-sorted equals* large-sorted))])) ;; wish list: ;; --------------------------------- ;; [List-of X] -> Boolean ;; does this list contain two items? (define (two? l) false) ;; [List-of X] -> Boolean ;; does this list contain exactly one item? (define (one? l) false)