Quicksort in LISP

问题:

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?

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

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

回答3:

(defun quick (list)
  (when (< = (length list) 1) (return-from quick list))
  (let ((pivot (car list)) (rest (cdr list)) (less nil) (greater nil))
    (loop for i in rest do
      (if (< i pivot) (push i less) (push i greater)))
    (append (quick less) (list pivot) (quick greater))))

回答4:

There are some errors in the program. The corrected program is:

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

回答5:

I'd recommend to change the code of liya babu/Will Ness like this:

(defun quick (list)
  (if (null list) nil
      (let ((pivot (first list)) (less nil) (greater nil))
        (dolist (i (rest list))
          (if (< i pivot) (push i less) (push i greater)))
        (append (quick less) (list pivot) (quick greater)))))

Although just slightly edited I find it both more lispy and more succinct.

回答6:

This should also work:

(defun qsort (l)
  (cond
   ((null l) nil)
   (t (append
       (qsort (car(list<> (car l)(cdr l))))
       (cons (car l) nil)
       (qsort (cadr(list<> (car l)(cdr l))))))))

(defun list<> (a b &optional rl rr)
    (cond
     ((null b) (list rl rr))
     ((<=(car b)a) (list<> a (cdr b) (cons (car b) rl) rr))
     (t (list<> a (cdr b)rl (cons (car b) rr)))))

(setq l (loop for j from 1 to 20 append (list(random 100))))
(qsort l)
;=> (86 99 9 31 66 58 57 43 48 21 51 0 32 69 39 47 59 76 69 23)
;=> (0 9 21 23 31 32 39 43 47 48 51 57 58 59 66 69 69 76 86 99)