Kenny Dewhirst

A little while back, I challenged myself to write a Scheme implementation of quicksort. After all, it’s a recursive algorithm, and Scheme is nothing if not recursive, and it seemed like a fun change of pace from writing algorithms in a procedural language.

; Quicksort a proper list
(define (quicksort lst)
  (cond
    ((null? lst)
     '())
    (else (append (quicksort (find-smaller-or-equal
                              (cdr lst) (car lst)))
                  (cons (car lst)
                        (quicksort (find-larger
                                    (cdr lst) (car lst))))))))

(define (find-larger lst lower-bound)
  (cond
    ((null? lst)
     '())
    ((<= (car lst) lower-bound)
     (find-larger (cdr lst) lower-bound))
    (else
     (cons (car lst)
           (find-larger (cdr lst) lower-bound)))))

(define (find-smaller-or-equal lst upper-bound)
  (cond
    ((null? lst)
     '())
    ((> (car lst) upper-bound)
     (find-smaller-or-equal (cdr lst) upper-bound))
    (else (cons (car lst)
                (find-smaller-or-equal (cdr lst) upper-bound)))))

I had a good time writing this, and it’s one of the shortest quicksorts I’ve seen, though I make no claims as to its efficiency.