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