### Simple destructive quicksort

Programming languages have become more expressive over time. Consider quicksort. Hoare's original version was quite difficult to understand - IIRC it wasn't even recursive. Nowadays the two-line quicksort is an icon of Haskell:

``````qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (>= x) xs)``````

Unfortunately it's also an icon of unrealistic examples - it makes too many passes over the lists, and conses far too much, so it isn't all that quick. The more efficient sorts don't make such impressive examples - especially the destructive ones, whose Haskell incarnations are infested with intimidating monads.

Here's a gem from the Pitmanual: a reasonably clear destructive quicksort in fifteen lines.

```Date: 9 September 1981 18:44-EDT
From: George J. Carrette <GJC>
To:   KMP
cc:   JAR

I think that the QUICKSORT properly coded is even shorter and neater than
the BUBBLESORT. It is also better for showing students since it is
naturally recursive, divide&conquer.

```(defmacro rplacd&pop (x &optional y)
`(rplacd (prog1 ,x (setq ,x (cdr ,x))) ,y))

(defun quicksort (list judge)
(if (null list)
()
(do ((proof (rplacd&pop list))
(goats ())
(sheep ()))
((null list)
(nconc (quicksort goats judge)
proof
(quicksort sheep judge)))
(if (funcall judge (car list) (car proof))
(setq goats (rplacd&pop list goats))
(setq sheep (rplacd&pop list sheep))))))``````

`rplacd&pop` captures the idea of destructively removing the first element of a list. It sounds like a nice example, since it uses a macro to express a by-reference operation in a language without by-reference parameters. But it's not really good for showing students, because it's not safe - it evaluates x twice and its subforms (if any) thrice. (Update 6 April: it uses `setq`, not `setf`, so it's ok in Maclisp, because it only works on variables. Even in Common Lisp it would only be a problem when used with a symbol-macro.) I don't know how to do it right in Maclisp, but in Common Lisp it requires the sort of macrology that inspires fear and loathing:

``````(defmacro rplacd&pop (x &optional y &environment e)
(multiple-value-bind (temps forms svars writeform readform)
(get-setf-expansion x e)
`(let* (,@(mapcar #'list temps forms)
This might be a good example of how to write `setf`-like macros, which is a confusing corner of Common Lisp that certainly deserves some examples. But it's no way to write a clear quicksort!
Of course, the simplest way for a language to make a realistic quicksort simple is to predefine `partition`. Is that cheating? I think it could be useful often enough to belong in a standard library. But to truly simplify quicksort down to a one-liner will require some advances in expressiveness, so we can write something closer to the natural definition: partition on the first element and recurse on both halves.