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