The Beauty of a Lisp Quicksort (Thursday, March 30, 2006)

I have discovered the definition of beauty... last night during a hideous exam for Advanced AI, we were instructed to port a very concise, elegant (if rather inefficient) version of Quicksort from a bizarre obscure programming language called Haskell into a similarly concise, elegant (if rather inefficient) version in Lisp. What I presented for my answer on the exam was good, but I have since come up with a thing of beauty. Quicksort in just a few lines of lisp... it may not be the most efficient, but it has to be the most concise. And it is also the first time in my life, that I have been able to reproduce Quicksort from memory. And here it is:

(defun quicksort (lis) (if (null lis) nil
  (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    (append (quicksort (remove-if-not fn r)) (list x)
      (quicksort (remove-if fn r))))))


Comments

Well, LISP is really good

It occurs to me that I mentioned this implementation wasn't the most efficient, but I'm surprised I forgot to explain why.

The first problem with this quicksort is that it always chooses the first item in the list as the pivot. For certain data, this can cause the efficiency to degenerate to O(n^2), which isn't very good, to say the least. The solution to this is to choose a random element as the pivot for each iteration. This has been shown to keep the efficiency at O(n log n) for any data.

The second way this implementation should be improved for a production system is to determine which sublist is shorter and which is longer, and make sure that the shorter one is done first and the longer one last, to take advantage of Lisp's ability to unwind tail recursion. It has been shown that this significantly reduces the depth of the recursion that is necessary — without bothering to write iterative code.

Oh how I love Lisp!

I hate lisp! Our teacher was crazy man - lisp-lover! May be I'm not right, but Ithink so!

It's truly beautiful! :)

How about this (also inefficient) Erlang implementation?

qsort([]) -> [];
qsort([Pivot|T]) ->
qsort([X || X <- T, X < Pivot])
++ [Pivot] ++
qsort([X || X <- T, X >= Pivot]).