冒泡排序常见的Lisp错误

Question

我正试图在Common Lisp中实现冒泡排序,而且我很难掌握我的方向.[见下文]是我到目前为止所得到的,据我所知,它遵循算法,但我'得到错误"使用arguments()调用未定义函数SORTED." 当我运行它.我似乎无法找到原因.

(defun bubble (lis)
  (let ((sorted nil) (j 0))
    (do () ((not sorted))
      (progn 
        (setf sorted t)
        (do (i j (+ i 1))
            (if (< (nth i lis) (nth (+ i 1) lis))
                (progn
                  (swap1 (lis (nth i lis) (nth (+ i 1) lis)))
                  (setf sorted nil)
                  )
              )
          )
        )
      )
    )
  )

Answer 1

每次调用NTH需要迭代列表.如果将列表视为向量,则可能应该使用向量.如果您并不真正关心效率,那么您可能仍然希望使用ELT而不是NTH,因为它ELT适用于任何类型的序列.这样,您可以传递矢量或列表,并且其中至少有一个可以很好地工作(只要冒泡排序可以有效).你最终可能会得到像Rosetta Code那样的东西.

顺便说一下,R​​osetta Code有一个列表迭代冒泡排序的例子,所以我不会复制它.相反,下面是一个递归版本,我改编自Prolog版本(罗马巴塔克).因此,它不一定更好,但它采用了多个值,ETYPECASE,DESTRUCTURING-BIND,...这显然不是通常教的功能.

(defun bubble-sort (list)
  (labels
      ((bsort (list acc)
         (etypecase list
           (null acc)
           (cons (destructuring-bind (head . tail) list
                   (multiple-value-bind (new-tail max)
                       (bubble head tail)
                     (bsort new-tail
                            (cons max acc)))))))
       (bubble (x list)
         (etypecase list
           (null (values nil x))
           (cons (destructuring-bind (y . tail) list
                   (multiple-value-bind (new-tail max)
                       (bubble (max x y) tail)
                     (values (cons (min x y) new-tail)
                             max)))))))
    (bsort list nil)))