我的Quicksort无法使用负数(Common Lisp)

Question

该功能只有正数才能正常工作.工作有时是负面但大部分时间显示此错误"值-1不是UNSIGNED-BYTE类型".

(defun OrdRapido (lista inf sup)
  (let ((pivote (nth sup lista)) (i (1- inf)) (j sup) (aux))
    (unless (>= inf sup)
        (loop (when (>= i j) (return))
          (loop (setf i (1+ i)) (when (>= (nth i lista) pivote) (return)))
          (loop (setf j (1- j)) (when (<= (nth j lista) pivote) (return)))
          (when (< i j)
            (setf aux (nth i lista))
            (setf (nth i lista) (nth j lista))
            (setf (nth j lista) aux)))  
        (setf aux (nth i lista))
        (setf (nth i lista) (nth sup lista))
        (setf (nth sup lista) aux) 
        (OrdRapido lista inf (1- i))
        (OrdRapido lista (1+ i) sup)) 
    lista)) 

例如:

(setq lista2 '(-5 3 7 6 2 1 -4 100 5 80 96 14 2 3 1 0 0 789 -1 3))
(OrdRapido lista2 0 (1- (length lista2)))

CL-USER> 
(-5 3 7 6 2 1 -4 100 5 80 96 14 2 3 1 0 0 789 -1 3)
CL-USER> 
(-5 -4 -1 0 0 1 1 2 2 3 3 3 5 6 7 14 80 96 100 789)

但不适用于此,我只添加 - 到80

'(-5 3 7 6 2 1 -4 100 5 -80 96 14 2 3 1 0 0 789 -1 3)

谢谢

更正的版本(随机支点添加),我知道有更好的方法,这只是一个教练离开的练习

 (defun OrdRapido (lista inf sup)
  (let ((pivote (nth (random (1+ sup)) lista)) (i inf) (j sup) (aux))
    (unless (>= inf sup)
        (loop (when (> i j) (return))
          (loop (when (<= (nth i lista) pivote) (return)) (setf i (1+ i)))
          (loop (when (>= (nth j lista) pivote) (return)) (setf j (1- j)))
          (when (<= i j)
            (setf aux (nth i lista))
            (setf (nth i lista) (nth j lista))
            (setf (nth j lista) aux)
            (setf i (1+ i))
            (setf j (1- j))))  
        (OrdRapido lista inf j)
        (OrdRapido lista i sup)) 
    lista))

Answer 1

您正在尝试返回列表中不起作用的第-1个元素.nth返回列表的第n个元素,因此(nth 0'(1 2 3))将返回1.但是在代码中的某个时刻它会调用(nth -1(-5 -80 -4 -1 0 0 ... ))和繁荣!

关于您的代码的其他说明:

• 将结束语放在单独的行上并不是好的lisp风格,并且使您的代码更难阅读.Lisp代码由列表组成,parens并不像其他语言的花括号.
• 使用支持您的语言的编辑器.我推荐带有Slim的Vim或带有粘液的Emacs.如果您使用带有粘液的emacs,此视频可能会帮助您开始使用.
• 不要在你的名字中使用骆驼套管.所有符号在共同口齿不清upcased它们实习时如此"HelloThere是完全一样的符号为" hellothere或"HELLOTHERE

另外,请查看rosettacode页面以获取quicksort,了解如何在common-lisp(以及许多其他语言)中执行此操作.

;; Here is a functional version for example.
(defun quicksort (list &aux (pivot (car list)) )
  (if (rest list)
      (concatenate 'list 
             (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
             (remove-if-not #'(lambda (x) (= x pivot)) list)
             (quicksort (remove-if-not #'(lambda (x) (> x pivot)) list)))
      list))

如果您不习惯阅读lambdas,那么这里的代码与上面的代码相同,但将lambdas制作成本地函数,因此代码读起来更像英语.

(defun quicksort (list &aux (pivot (car list)))
  (labels ((less-than-pivot (x) (< x pivot))
           (greater-than-pivot (x) (> x pivot))
           (equal-to-pivot (x) (= x pivot)))
    (if (rest list)
        (concatenate 'list 
                     (quicksort (remove-if-not #'less-than-pivot list))
                     (remove-if-not #'equal-to-pivot list)
                     (quicksort (remove-if-not #'greater-than-pivot list)))
        list)))

第二个版本在我的脑海里不那么整洁.在这两个示例中,您都可以看到递归方法如何让您考虑如何只执行一个步骤,然后通过调用自身,您将解决方案应用于一个步骤以获得整个问题的解决方案