Lisp quicksort code

I would really appreciate it if someone could review my quicksort implementation. Additionally, I generated my list dynamically and wrote a couple of tests. Of course, I realize that the tests are not complete, but I decided to stop where I was and see if I could get some feedback.

(defun categorize_list(pivot thelist less more)
(let ((comparee (car thelist)) (therest (cdr thelist)))
(if (null thelist)
(list less more)
(if (< comparee pivot)
(categorize_list pivot therest (append less (list comparee)) more)
(categorize_list pivot therest less (append more (list comparee)))
)
)
)
)

(defun quicksort(thelist)
(if (null thelist)
()
(let (
(pivot (car thelist))
(therest (cdr thelist))
)
(let ((categorized_list (categorize_list pivot therest () ())))

(append (quicksort (nth 0 categorized_list)) (list pivot) (quicksort (nth 1 categorized_list)))
)
)
)
)

(defun make_list(thelist remaininglength)
(if (eq remaininglength 0)
thelist
(make_list (append (list (random 25)) thelist) (- remaininglength 1))
)
)

(defun should_be_least_to_greatest(thelist)
(if (< (length thelist) 2)
nil
(if (<= (nth 0 thelist) (nth 1 thelist))
(should_be_least_to_greatest (cdr thelist))
(error "Out of order: ~d !< ~d ~%" (nth 0 thelist) (nth 1 thelist))
)
)
)

(defun test_should_become_in_order(thelist)
(let ((sortedList (quicksort thelist)))
(format t "IN: ~a ~% SD: ~a ~% Testing sort.~%" thelist sortedList)
(should_be_least_to_greatest sortedList)
)
)

(defun test_should_maintain_length(thelist)
(if (not (eql (length thelist) (length (quicksort thelist))))
(error "The sorted list is a different length than the original list! ~%")
)
)

(let ((thelist (make_list () 10)))
(test_should_become_in_order thelist)
(test_should_maintain_length thelist)
)

• Asymptotically, this isn't a quicksort... appending lists the way you do it makes it more expensive than the textbook version. This also conses a lot of memory. Quicksort is best suited for in-place updates of arrays with O(1) random access cost, it's not so great for lists. I think most Lisp implementations use mergesort for Lists. Dec 27, 2014 at 9:30

I don't know what the policy is about where/how to put subsequent code reviews, since the Stackexchange system doesn't really seem well-suited to their threadlike nature. Anyway, here goes.

(let ((pivot (car the-list)) (the-rest (cdr the-list)))
(let ((categorized-list (categorize-list pivot the-rest () ())))


Look up LET*.

(let ((the-list ()))
(loop for l from 1 to length do (setq the-list (append the-list (list (random 25))))) the-list))


This seems pretty awkward. It's just:

(loop for l from 1 to length collect (random 25))


And here:

(loop for l from 0 to (- (length the-list) 2) do
(unless (<= (nth l the-list) (nth (+ l 1) the-list)) (error "Out of order: ~d < ~d ~%" (nth l the-list) (nth (+ l 1) the-list)))))


Every call to LENGTH or NTH has to walk the linked list. You don't want to do that in a loop. (I think you should not often need NTH with lists, and almost never in a loop.)

(loop for p on the-list while (second p)
when (< (second p) (first p))
do (error "Out of order: ~d < ~d~%" (second p) (first p)))


If you're going to be writing Common Lisp code, it pays to learn the LOOP DSL (or ITERATE, its spiritual successor).

Other random things:

• Your code has gotten a lot ... wider. While I appreciate taking fewer lines, there's a limit. I don't often see multiple LET bindings on one line, for example.
• You sometimes still leave out the space before a paren, like list(pivot, which looks funny to me.

Your formatting is weird. It's going to be a lot easier for other programmers to read your code if you use a more standard style. For example, you have lots of lines with nothing but a hanging parenthesis. Your functions have no docstrings. Sometimes you use_underscores and sometimes you use compoundwords but the Lisp style is hypenated-words. Your indentation is inconsistent: learn the command in your text editor to indent your source code for you, and use it.

(if (not (eql (length thelist) (length (quicksort thelist))))


Using EQL for numbers seems odd. I think = would be preferred. An IF with only one branch is strange, too: WHEN or UNLESS tends to be preferred. Thus:

(unless (= (length thelist) (length (quicksort thelist)))


In another place, you do a comparison with:

(eq remaininglength 0)


The behavior of EQ with integers is undefined. You can use = or in this case:

(zerop remaininglength)


You're using recursion a lot even when it's not needed, e.g., in make_list and should_be_least_to_greatest. Common Lisp doesn't require tail-call optimization, and it's not generally common style. LOOP (or ITERATE) would probably be simpler and more efficient here.

You walk a list applying <=. Lisp's <= already takes any number of arguments, so if you don't need to know the specific elements which are out of order, you can just apply it once.

You have several negative conditionals, which is a bad idea in any language.

(if (null thelist)
()


I'd change it to:

(defun quicksort(thelist)
(unless (null thelist)
; Sort list
) ; Pardon the dangling ), but there's a comment on the last line

• That doesn't bother me as much: it's making the "return an empty list" case clear.
– Ken
Mar 5, 2011 at 15:42