Steven Goss over at the zero bit stream has another great Common Lisp post. His idea is to compare a minimal Haskell Quicksort routine to the same function written in Common Lisp. A case can be made that the result is not really Quicksort in either language because of the performance profile but they do follow the Quicksort algorithm and are interesting even if they aren’t useful as production code.
Goss’s final result makes use of a list comprehension macro that is interesting in its own right but the first attempt is also nice. Here’s Goss’s code for the first attempt:
(defun quicksort (list) (when list (destructuring-bind (p . xs) list (let ((lesser (remove-if-not (lambda (x) (< x p)) xs)) (greater (remove-if-not (lambda (x) (>= x p)) xs))) (append (quicksort lesser) (list p) (quicksort greater))))))
Notice how it makes the structure of the Quicksort algorithm explicit. Of course it doesn’t choose the pivot in an intelligent way—which can result in n2 behavior—and all those remove-if-not and appends are each tacking on O(n) penalties but you still have to love the beauty and brevity of the code.
Quicksort, like any other industrial strength algorithm, is hard to get right. As I mentioned in my post on Jon Bentley, perfecting the Quicksort algorithm is definitely not trivial. This implementation doesn’t come close but it is useful because it makes the structure of Quicksort clear and because it shows how Common Lisp can express algorithms in a beautiful way.