Lisp quicksort code

Question

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

Answer 1

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.

Answer 2

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.

Instead of:

(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.

Answer 3

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