About me

About me


RSS feed

Shortest quicksort

8th September 2020

In an earlier post I proposed the challenge of writing the shortest Common Lisp function to sort a list of numbers into ascending order: Shortest sort answers.

I was recently experimenting with applying the same challenge to a quicksort. For example:

CL-USER > (quicksort '(3 1 4 1 5 9 2 6 5 3 5 8))
(1 1 2 3 3 4 5 5 5 6 8 9)

The solution can use any Common Lisp functions you want, apart, of course, from sort or stable-sort.

To get the score, count the non-nil atoms in the function definition(s) using count-atoms:

(defun count-atoms (form)
  (typecase form
    (null 0)
    (atom 1)
    (cons (+ (count-atoms (car form))
             (count-atoms (cdr form))))))

Best solution

Here's the best solution that I've found, with a count of 28 non-nil atoms:

(defun quicksort (lis)
  (when lis
    (destructuring-bind (p . r) lis
      (flet ((less (x) (< x p)))
        (append (quicksort (remove-if-not #'less r))
                (list p)
                (quicksort (remove-if #'less r)))))))

It works as follows:

  • Choose a 'pivot' element p in the list to be sorted and remove it from the list to give a list r. For simplicity this function chooses the first item in the list as the pivot.
  • Split r into two lists: a, containing all the elements less than p, and b, containing all the elements greater than or equal to p.
  • Recursively call quicksort on a and b.
  • The result is got by appending a, (list p), and b.

Can you improve on this solution?

blog comments powered by Disqus