冒泡排序 Common Lisp 错误

问题描述 投票：0回答：4

我正在尝试在 Common Lisp 中实现冒泡排序，但我很难确定自己的方位。[见下文]是我到目前为止所得到的，据我所知，它遵循算法，但是我收到错误“使用参数 () 调用未定义的函数 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)
                  )
              )
          )
        )
      )
    )
  )
sorting common-lisp bubble-sort
4个回答
5
投票

每次调用 

NTH
都需要迭代列表。如果将列表视为向量，则可能应该使用向量。如果您并不真正关心效率，您可能仍然想使用 
ELT
 而不是 
NTH
，因为 
ELT
适用于任何类型的序列。这样，您可以传递向量或列表，并且至少其中一个可以很好地工作（就冒泡排序的效率而言）。 您最终可能会得到类似于Rosetta Code中的东西。

顺便说一下，Rosetta Code 有一个列表迭代冒泡排序的例子，所以我就不复制了。相反，下面是我根据 Prolog 版本（由 Roman Barták）改编的递归版本。因此，它不一定更好，但它使用多个值，

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)))
4
投票

我们可以做很多事情来改进这段代码。

您可以采取一些措施来改善您的问题。如果您再次询问，请提供测试用例和具体问题。

  1. 缩进

    Lisp 的语法相对较少，但我们使用缩进来帮助突出代码的结构。大多数了解 Lisp 的编辑器都会帮助管理这个问题。与传统缩进方法最明显的不同是下面几行的右括号。我缩进了 mergelist 函数以显示更易读的函数体 - 嗯，至少对我来说是这样。

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

  2. 循环与DO

DO 在 lisp 中有着悠久的血统，但说实话，我用 DO 总是犯错误，所以不经常使用它。我永远不记得返回表格去哪里，增量。我倾向于使用LOOP

但首先，我们不需要使用 progn。大多数循环结构对于它们正在迭代的代码都有一个隐式 progn，所以

(defun bubble-1 (lis)
  (let ((sorted nil) (j 0))
    (do () ((not sorted))

      (setf sorted t)
      (do (i j (+ i 1))
      (if (< (nth i lis) (nth (+ i 1) lis))
          (swap1 (lis (nth i lis) (nth (+ i 1) lis)))
          (setf sorted nil))))))

稍微好一点。查看您的代码，其中有对 swap1 的调用，它必须是某处提供的 defun 。此行还存在语法问题，因为“lis”显示为函数调用。

让我们尝试评估该函数，看看会发生什么

; in: DEFUN BUBBLE-1
;     (LET ((SORTED NIL) (J 0))
;       (DO ()
;           ((NOT SORTED))
;         (SETF SORTED T)
;         (DO (I
;              J
;              (+ I 1))
;             (IF (< # #) (SWAP1 #) (SETF #)))))
; 
; caught STYLE-WARNING:
;   The variable J is defined but never used.

; in: DEFUN BUBBLE-1
;     (DO (I
;          J
;          (+ I 1))
;         (IF
;          (< (NTH I LIS) (NTH (+ I 1) LIS))
;          (SWAP1 (LIS (NTH I LIS) (NTH # LIS)))
;          (SETF SORTED NIL)))
; --> BLOCK 
; ==>
;   (LET (I J (+ I))
;     (TAGBODY
;       (GO #:G3)
;      #:G2
;       (TAGBODY)
;       (PSETQ + 1)
;      #:G3
;       (UNLESS IF (GO #:G2))
;       (RETURN-FROM NIL (PROGN (< # #) (SWAP1 #) (SETF #)))))
; 
; caught WARNING:
;   undefined variable: I

; --> BLOCK LET TAGBODY UNLESS 
; ==>
;   (IF IF
;       NIL
;       (GO #:G2))
; 
; caught WARNING:
;   undefined variable: IF

;     (LIS (NTH I LIS) (NTH (+ I 1) LIS))
; 
; caught STYLE-WARNING:
;   undefined function: LIS

;     (SWAP1 (LIS (NTH I LIS) (NTH (+ I 1) LIS)))
; 
; caught STYLE-WARNING:
;   undefined function: SWAP1
; 
; compilation unit finished
;   Undefined functions:
;     LIS SWAP1
;   Undefined variables:
;     I IF
;   caught 2 WARNING conditions
;   caught 3 STYLE-WARNING conditions`enter code here`

哇。这告诉我们一些事情

  1. 嵌套DO中的变量J没有被使用。删除它。

  2. 嵌套循环中的 DO 语法是错误的。它需要是一般形式

    (DO ((var init step))
    (termination-test result-form)
  statement)

嵌套 do 缺少终止测试。此外，i 的变量声明缺少初始化。

  1. Let有点多余，你可以将sorted的声明移到do中

    (do ((sorted nil)) ((not sorted ) ... )

  2. 表格

    (SWAP1 (LIS (NTH I LIS) (NTH (+ I 1) LIS)))

有两个问题。首先 SWAP1 未定义。其次，形式 (LIS (NTH I LIS) (NTH (+ I 1) LIS)) 不可能是正确的，因为 LIS 出现在函数调用位置。出现在表单前面的任何内容都必须是函数。在这种情况下，LIS 是一个参数。

幸运的是，Common Lisp 有一个内置函数，可以为我们交换值 - 它称为rotatef。所以整个表格需要看起来像 

(rotatef (nth I lis) (nth (1+ i) lis))
  1. 函数一旦运行，do中就没有结果形式，因此排序后的数组永远不会返回给调用者。您将看不到任何输出。您需要考虑这里有嵌套循环的事实。

我会考虑一下你的算法。正如 Zephyr Pellerin 上面所说，递归解决方案会更好，所以除非您的任务是使用迭代解决方案

1
投票

您应该研究 David Hodge 的答案，其中详细介绍了代码的所有问题。在这里，我提供了使用 

do
特殊形式的冒泡排序的迭代版本。与您尝试用代码实现的算法的唯一主要区别是使用变量 
end
，该变量每次都会递减以减少测试数量：

(defun bubble (lis)
  (let ((sorted nil)
        (end (length lis)))
    (do () (sorted lis)
      (setf sorted t)
      (decf end)
      (do ((i 0 (1+ i)))
          ((>= i end))
        (when (< (nth i lis) (nth (1+ i) lis))
          (rotatef (nth i lis) (nth (1+ i) lis))
          (setf sorted nil))))))
0
投票

(defun bubble_move (l)
  (cond
   ((atom (cdr l)) l)
   ((> (car l) (cadr l)) (cons (cadr l) (bubble_move (cons (car l) (cddr l)))))
   (T l)
  )
)

(defun bubble (l)
  (cond
   ((atom (cdr l)) l)
   (T (bubble_move (cons (car l) (bubble (cdr l)))))
  )
)

(bubble '(5 4 3 2 1))

很久以前写这个只是为了好玩，但偶尔发现你的问题

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.