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