swisspig.net - To hell with the pig... I'm going to Switzerland.

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

—Brian (3/30/2006 11:57 AM)
(13 comments)

Comments

Well, LISP is really good

-- Alexander (3/30/2007 8:23 AM)

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!

-- Brian (3/30/2007 10:40 PM)

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

-- Kabait (6/21/2008 9:41 AM)

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

-- André Laszlo (9/27/2008 1:42 PM)

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.

-- Jon Chu (2/2/2011 10:11 PM)

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.

-- Brian (2/3/2011 12:11 AM)

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

-- Emeka (2/3/2011 12:45 AM)

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

-- Eric O'Connor (2/9/2011 8:18 AM)

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

-- lamer (7/7/2012 8:37 AM)

haskell wins

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

-- tkd (11/15/2012 11:29 AM)

or, alternatively,

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

-- tkd (11/15/2012 11:34 AM)

I'm wondering whether the median-of-three method to choose the pivot from three list elements picked randomly

-- Bill McEnaney (11/15/2014 12:40 AM)

Bill, as far as I know, the typical median-of-three approach uses the first element, the last element, and the middle element (using integer length/2 as the index of the middle element). Generally, for quicksort, the optimal pivot is the actual median of all the values, but that would require O(n) to find, while median-of-three gives a good enough approximation in O(1). See "Algorithms in C" by Sedgewick, who came up with this approach.

-- Brian (11/15/2014 12:06 PM)

Name
URL
Comment
(no html)
 

Disclaimer: Opinions on this site are those of Brian Ziman and do not necessarily
reflect the views of any other organizations or businesses mentioned.