Quicksort in LISP

Question

I am trying to do a quicksort using LISP but I am having trouble with my functions output.

(defun qsort (L)
   (cond
   ((null L) nil)
   (t(append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or(null a)(null b) nil))
    (( < a (car b)) (list< a (cdr b)))
    (t(cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or( null a)(null b) nil))
    (( >= a (car b)) (list> a (cdr b)))
    (t(cons (car b) (list> a (cdr b))))))   

My problem being when list< and list>= finish the list always ends with a .T. For instance:

> (list< '4 '(1 5 3 8 2))
Entering: LIST<, Argument list: (4 (1 5 3 8 2))
 Entering: LIST<, Argument list: (4 (5 3 8 2))
  Entering: LIST<, Argument list: (4 (3 8 2))
   Entering: LIST<, Argument list: (4 (8 2))
    Entering: LIST<, Argument list: (4 (2))
     Entering: LIST<, Argument list: (4 NIL)
     Exiting: LIST<, Value: T
    Exiting: LIST<, Value: (2 . T)
   Exiting: LIST<, Value: (2 . T)
  Exiting: LIST<, Value: (3 2 . T)
 Exiting: LIST<, Value: (3 2 . T)
Exiting: LIST<, Value: (1 3 2 . T)
(1 3 2 . T)

Why is (4 NIL) evaluating as T?

Answer 1

Your problem with list<, and also with list>=, lies on ((or ( null a)(null b) nil)), it should be (( or( null a)(null b)) nil). Note nil was moved outside of the condition to be the returned value.

Furthermore, on the definition of list>= you are calling list>, but I'm positive you meant list>= instead.

I would also suggest some indentation to address the legibility of lisp, like follows

(defun qsort (L)
  (cond
    ((null L) nil)
    (t
      (append
        (qsort (list< (car L) (cdr L)))
        (cons (car L) nil) 
        (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((< a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((>= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))

Some testing follows:

(list< '4 '(1 5 3 8 2))
=> (1 3 2)

(list>= '4 '(1 5 3 8 2))
=> (5 8)

(qsort '(1 5 3 8 2))
=> (1 2 3 5 8)

Answer 2

Lisp has different kinds of collections. I think sort a list using quick-sort is not a good choice. In the implementation of STL in C++, the sorting method of list is merge-sort. I have tried to implement a 3-way quick-sort using the collections of array.

(defun quick-sort (arr start end)
  "Quick sort body"
  (if (< start end)
  (let ((n-pair (partition arr start end)))
  (quick-sort arr start (car n-pair))
  (quick-sort arr (cdr n-pair) end))
))

(defun partition (arr start end)
 "Partition according to pivot."
 (let ((pivot (aref arr start)) (cur start))
 (loop while (<= start end) do
  (cond
    ((< pivot (aref arr start)) ; pivot < arr[start], swap with arr[end]
     (swap arr start end) (decf end))
    ((> pivot (aref arr start)) ; pivot > arr[start], swap with arr[start]
     (swap arr cur start) (incf cur) (incf start))
    (t                          ; otherwise
     (incf start))))
    (cons (decf cur) start)))

(defun swap (arr i j)
 "Swap element of arr"
 (let ((tmp (aref arr i)))
 (setf (aref arr i) (aref arr j))
 (setf (aref arr j) tmp)))