 
swisspig.net about contact terms of use privacy policy activity site map 
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:
CommentsWell, 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.  Brian (3/30/2007 10:40 PM)
I hate lisp! Our teacher was crazy man  lisplover! May be I'm not right, but Ithink so!  Kabait (6/21/2008 9:41 AM)
It's truly beautiful! :)  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.  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 bestof3 quicksort when sorting primitives.  Brian (2/3/2011 12:11 AM)
defn partify [myfirst coll]  Emeka (2/3/2011 12:45 AM)
You never actually write in bare CL, so this is more representative: (and generic too!)  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 bogosort  lamer (7/7/2012 8:37 AM)
haskell wins  tkd (11/15/2012 11:29 AM)
or, alternatively,  tkd (11/15/2012 11:34 AM)
I'm wondering whether the medianofthree 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 medianofthree 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 medianofthree 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)
I recently learned python, which also has a simple naive implementation: def Qs(lis): if len(lis) <= 1: return lis return Qs([n for n in lis[1:] if n < lis[0]]) + [lis[0]] + Qs([n for n in lis[1:] if n >= lis[0]])  Brian (5/30/2015 11:45 PM)

All material copyright © 19952015 by
Brian Ziman, unless otherwise noted.
Disclaimer: Opinions on this site are those of Brian Ziman and do not necessarily
reflect the views of any other organizations or businesses mentioned. 