Home > Project > Quicksort in Scheme

## Quicksort in Scheme

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.