Page History

;; insertion sort
(define (isort alon)
  (cond [(empty? alon) empty]
        [(cons? alon)  (insert (first alon) (isort (rest alon)))]))

(define (insert new sortedlon)
  (cond [(empty? sortedlon) (list new)]
        [else (if (< new (first sortedlon))
                  (cons new sortedlon)]
                  (cons (first sortedlon) (insert new (rest sortedlon))))]))

;; quicksort (adapted to functional lists)
(define (qsort alon)
  (cond [(empty? alon) empty]
        [(cons? alon)
         (local [(define pivot (first alon))
                 (define other (rest alon))
                 (define lesser (filter (lambda (n) (<= n pivot)) other))
                 (define greater (filter (lambda (n) (> n pivot)) other))]
           (append (qsort lesser) (list pivot) (qsort greater)))]))