@ 9d8c149e89e015823df22a42b5d70029e7e44e25 | history
; quicksort.gov.lisp: sort a list of numbers.
;
; There are no loops and no mutation, so everything is recursion over
; lists. Definitions are sequential, so each helper comes before the
; functions that use it.
(define append
(lambda (a b)
(if (== a '())
b
(cons (car a) (append (cdr a) b)))))
; filter keeps the elements of l for which (keep x) is true.
(define filter
(lambda (keep l)
(if (== l '())
'()
(if (keep (car l))
(cons (car l) (filter keep (cdr l)))
(filter keep (cdr l))))))
; Partition around the first element, sort each side, and join them. The
; inner lambda binds pivot and rest; the two lambdas passed to filter are
; closures over pivot.
(define quicksort
(lambda (l)
(if (== l '())
'()
((lambda (pivot rest)
(append (quicksort (filter (lambda (x) (< x pivot)) rest))
(cons pivot (quicksort (filter (lambda (x) (>= x pivot)) rest)))))
(car l)
(cdr l)))))
(quicksort '(3 1 4 1 5 9 2 6 5 3 5))
(quicksort '(2.5 -1 0 7 -3.25))