Lisp 中的快速排序奇怪的行为？

Question

我设法使我的快速排序功能正常工作，但我很困惑为什么代码的轻微更改会导致该功能表现异常。这是工作代码：

(defun low (mylist)
  (setq result (list))
  (loop
      for x in mylist
      do (if (< x (car mylist))
             (setq result (cons x result))))
  result)

(defun high (mylist)
  (setq result (list))
  (loop
      for x in mylist
      do (if (> x (car mylist))
             (setq result (cons x result))))
  result)

(defun qsort (mylist)
  (if (null mylist)
       nil
       (progn 
         ;(setq l1 (low mylist))
         ;(setq l2 (high mylist))
         (append (qsort (low mylist))
                 (list (car mylist))
                 (qsort (high mylist))))))

但是在 qsort 函数中，如果我尝试将分区存储在 l1 和 l2 中然后调用 qsort 该函数不再有效：

(defun qsort (mylist)
  (if (null mylist)
      nil
      (progn 
        (setq l1 (low mylist))
        (setq l2 (high mylist))
        (append (qsort l1)
                (list (car mylist))
                (qsort l2)))))

有了这个(qsort (list -3 5 4 3 1 2))returns(-3 1 2)

我知道事先存储分区不是必需的，但为什么这不起作用？

Answer 1

问题是您在 Common Lisp 中使用了不正确的变量——这在大多数实现中都会发出信号：

CL-USER> (defun low (mylist)
           (setq result (list))
           (loop for x in mylist do 
              (if (< x (car mylist)) 
                (setq result (cons x result))))
           result)
;Compiler warnings :
;   In LOW: Undeclared free variable RESULT
LOW

请注意，编译器会给您警告，而不是错误，原因有二：

后面可以引入一个全局变量result，函数执行就正确了；
(setq x y) 的语义是这样的，如果没有定义变量 x，那么值 y 被分配给 symbol x，从某种意义上说，它是一种全局变量。

由于第二个原因，您的函数无法正常工作，因为在您的递归定义中，您使用 l1 和 l2 就好像它们是局部变量一样，用不同的实例化每次递归调用时的值，而它们是在不同调用之间全局分配的，从而产生不正确的结果。

有关该主题的更详尽的讨论，例如参见 [=30=]。

解决方法

您应该在使用前以 let 特殊形式引入局部变量。例如，您可以这样编写函数 low：

(defun low (mylist)
   (let ((result (list)))
     (loop for x in mylist  
        if (< x (car mylist)) 
        do (setq result (cons x result)))
     result))

let 引入了新变量，您稍后可以使用 setq 运算符对其进行赋值。例如，这里是 qsort 的正确版本：

(defun qsort (mylist)
    (if (null mylist) 
        nil
        (let ((l1 (low mylist))
              (l2 (high mylist)))
          (append (qsort l1) (list (car mylist)) (qsort l2)))))

最后，请注意，您可以用这种方式更简洁、更地道地编写函数 low（high 也类似）：

(defun low (mylist)
  (loop for x in mylist
     when (< x (car mylist))
     collect x))

最后的笔记

你的算法（和我的重写）没有正确排序列表，因为它消除了重复元素（例如尝试将它应用到列表 (7 3 2 2 4 9 1)）。

纠正它的一种方法是修改两个辅助函数之一，以便获得所有元素，例如，小于或等于子列表的汽车。这是生成正确算法的 low 函数的重写：

(defun low (mylist)
  (loop for x in (cdr mylist)
     when (<= x (car mylist))
     collect x))

Answer 2

正如 Renzo 所回答的那样，l1 和 l2 是全局变量。如果您通过 qsort 的定义跟踪它们的值，您将获得调用 (qsort '(-1 4 2 3 0 1)):

的以下跟踪

L1 = NIL L2 = (1 0 3 2 4)
L1 = (0) L2 = (4 2 3)
L1 = NIL L2 = NIL
(-1 0 1)

同时，如果您使用 let 形式，跟踪显示：

L1 = NIL L2 = (1 0 3 2 4)
L1 = (0) L2 = (4 2 3)
L1 = NIL L2 = NIL
L1 = (3 2) L2 = NIL
L1 = (2) L2 = NIL
L1 = NIL L2 = NIL

因此，l1 和 l2 在递归调用中被分配到 NIL 更深的位置，而在其顶部，它们的值应包含 non-empty 列表。

一般来说，混合递归（阅读函数式编程）和赋值是个坏主意。

Answer 3

Renso 有答案，但既然您已经在使用 loop，您应该挖掘它的潜力。因此你可以这样做

(defun partition (number-list pivot)
  (loop :for number :in number-list
        :if (<= number pivot)
            :collect number :into small
        :else
            :collect number :into large
        :finally (return (values small large))))

qsort 可以这样做来利用它：

(defun qsort (number-list)
  (if (not (cdr number-list))
      number-list
      (multiple-value-bind (small large)
                           (partition (cdr number-list) 
                                      (car number-list))
        (nconc (qsort small) 
               (list (car number-list))
               (qsort large)))))

Lisp 中的快速排序奇怪的行为？

Quicksort in Lisp Strange behavior?

lisp

common-lisp

quicksort