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]).

Just a small correction, Quicksort is O(n^2) no matter what you do. Doing a randomized quicksort only gives you O(nlogn) expected time. The worst case is still O(n^2) but most of us ignore that because it happens with low probability. If you did not randomize quicksort, the average case is still O(nlogn). However, an adversary could give you an input that always guarantees bad running time.

Unix uses a best of 3 quicksort which takes the the median of 3 random elements as a pivot. This is another form of randomized quicksort, which, although faster by a constant, is still O(nlogn) expected.

Of course, you only want to use Quicksort on stuff like numbers. Quicksort is not a stable sort, which means that items whose keys are the same may end up in a different order than they original were. Which is why Java, for example, uses a Merge sort when sorting instances of Comparable, and your best-of-3 quicksort when sorting primitives.

defn partify [my-first coll]
(let [greater (filter #( < my-first %) coll)
less (filter #(> my-first %) coll)]
[greater less] ))
(defn qsort [coll]
(let [my-first (first coll)
[greater less] (partify my-first (rest coll))
less-count (count less)
greater-count (count greater)]
(concat (if (>= less-count 2) (qsort less) less) [my-first] (if (>= greater-count 2) (qsort greater) greater)))

Clojure version, still not efficient

You never actually write in bare CL, so this is more representative: (and generic too!)

(defun quicksort (list &optional (cmp #\'<))
(when list
(list (quicksort (filter (cdr list) cmp) cmp)
(car list)
(quicksort (filter (cdr list) (compose #\'not cmp)) cmp))))

ohhhh...lisp can be so hard for beginners, all i can achive now is bubble sort, which is still better as bogo-sort

(defun swap(lst i j)
(rotatef (nth i lst) (nth j lst))
)

(defun bubble-sort(lst)
(dotimes (i (list-length lst))
(dotimes (j (list-length lst))
(if (< (elt lst i) (elt lst j))
(swap lst i j)
)
)
)
)

haskell wins

qsort [] = []
qsort (p:xs) = qsort [x|x<-xs, x<p] ++ [p] ++ qsort [x|x<-xs, x>=p]

or, alternatively,

qsort [] = []
qsort (p:xs) = smaller ++ [p] ++ bigger
where
smaller = filter (< p) xs
bigger = filter (>= p) xs