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:
—Brian (3/30/2006 11:57 AM)
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.
-- 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! :)
-- 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 best-of-3 quicksort when sorting primitives.
-- Brian (2/3/2011 12:11 AM)
defn partify [my-first 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 bogo-sort
-- lamer (7/7/2012 8:37 AM)
-- tkd (11/15/2012 11:29 AM)
-- 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)
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]) + [lis] + Qs([n for n in lis[1:] if n >= lis])
-- Brian (5/30/2015 11:45 PM)
Disclaimer: Opinions on this site are those of Brian Ziman and do not necessarily
reflect the views of any other organizations or businesses mentioned.