LISP中的快速排序

Question

我正在尝试使用LISP进行快速排序，但我遇到了我的函数输出问题。

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

我的问题是，当列表<和列表> =完成列表总是以.T结束。例如：

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

为什么（4 NIL）评估为T？

Answer 1

您的问题list<，还有list>=，位于((or (null a)(null b) nil))，它应该是((or(null a)(null b)) nil)。注意nil已被移出条件以作为返回值。

此外，关于list>=的定义，您正在调用list>，但我确定您的意思是list>=。

我还建议一些indentation解决口齿不清的可读性，就像如下

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

一些测试如下：

(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有不同类型的集合。我认为使用快速排序来排序并不是一个好的选择。在C++中实现STL时，list的排序方法是merge-sort。我试图使用数组的集合来实现3路快速排序。

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

Answer 3

程序中有一些错误。校正程序是：

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

Answer 4

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

Answer 5

这也应该工作：

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