Josh Stone, Blog

Josh’s projects and security nerdery

Quick Quicksort

Just prowling around today, I found a couple interesting pages on Haskell. I am thinking about trying it out a bit, just to see what I can learn. At any rate, on one of the intro documents I found the following code snippet:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

(135 chars)

“Wow,” I thought. That’s pretty cool. Especially compared to the C version on the same page (451 chars). That one brought back memories of coding merge sort as a freshman at Tech.

So I got to thinking… what does quicksort look like in Common Lisp? I googled a bit, and found some code here(549 chars!) and here(376 chars!). I’m sure they are quite efficient, but for the purposes of my little journey, they failed miserably — too verbose!

So here is the best I can come up with — I am sure that there is a shorter way, but this sufficies:

(defun qsort (lst)
  (if lst
      (let ((f #'(lambda (y) (> y (car lst)))))
    `(,@(qsort (remove-if f (cdr lst)))
      ,(car lst)
      ,@(qsort (remove-if-not f (cdr lst)))))
    '())) 

Down to 190 chars.

I could move a couple lines up and cheat, but I think it’s good for now.