About me

About me

Feeds

RSS feed

Shortest sort answers

24th April 2018

A week ago I presented a challenge of finding the shortest Common Lisp function to sort a list of numbers into ascending order, without using sort or stable-sort

The size was to be evaluated by counting 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))))))

Here's a summary of the contributed answers :

Selection sort (20)

When I presented the challenge the answer I had in mind was:

(defun mysort (lst)
  (if (null lst) nil
    (let ((min (apply #'min lst)))
      (cons min (mysort (remove min lst :count 1))))))

which has a score of 20. This recursively extracts the smallest number and puts it at the beginning of the sorted list of the remaining items.

Rainer Joswig pointed out on Twitter that apply should be replaced with reduce, because apply is limited to the number of arguments specified by CALL-ARGUMENTS-LIMIT.

Version using loop (23)

For those who like loop, alandipert suggested the following similar solution:

(defun mysort (xs)
  (loop while xs
        for x = (reduce #'min xs)
        do (setq xs (remove x xs :count 1))
        collect x))

So loop isn't always more concise than the standard lisp alternative.

Selection sort (19)

Faré suggested you can reduce the size by replacing:

(if (null lst) nil ...

with

(and lst ...

Although this saves two tokens it only reduces the score by 1 because count-atoms ignores nil.

So the best answer so far is:

(defun mysort (lst)
  (and lst
       (let ((min (reduce #'min lst)))
         (cons min (mysort (remove min lst :count 1))))))

Merge sort (27)

Although efficiency wasn't a consideration of the original challenge Faré provided a more efficient merge sort with N log N speed and a score of 27:

(defun mysort (l)
(let ((half (ash (length l) -1)))
(if (zerop half) l
(merge (type-of l)
(mysort (subseq l 0 half))
(mysort (subseq l half)) '<))))

Insertion sort (16)

Finally leaving the best to last; the previous solution suggested the following, which has the best score of 16 (until someone beats it!):

(defun mysort (lst)
  (and lst
       (merge 'list 
              (list (car lst)) 
              (mysort (cdr lst)) #'<)))

It places each element at the correct position in the sorted list of elements processed so far. It relies on the fact that if merge is given two lists that are already sorted by the predicate the result is a sorted list. A list of one element is trivially already sorted, and the list returned by the recursive call to mysort is also, by definition, already sorted; QED.


blog comments powered by Disqus