My Quicksort doesn't work with negative numbers (Common Lisp)

Question

The function works fine with only positive number. Works sometimes with negative but most of the time show this error "The value -1 is not of type 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)) 

For example:

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

But doesn't work with this, and I only add the - to 80

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

Thanks

Corrected version (random pivot added), I know there are better ways, It's just an exercise the profesor left

 (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

You are trying to return the -1th element of a list which won't work. nth returns the nth element of the list so (nth 0 '(1 2 3)) will return 1. But at some point in your code it calls (nth -1 (-5 -80 -4 -1 0 0 ...)) and boom!

Other notes about your code:

• Putting the closing ) on a seperate line is not good lisp style and makes your code harder to read. Lisp code is made of lists, the parens are not really like the curly braces of other languages.
• Use an editor that supports your language. I recommend Vim with Slim or Emacs with slime. If you use emacs with slime this video may help you get started.
• Dont use camel casing in your names. All symbols are upcased in common lisp when they are interned so 'HelloThere is EXACTLY the same symbol as 'hellothere or 'HELLOTHERE

Also please look at the rosettacode page for quicksort to see how to do it in common-lisp (and lots of other languages).

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

If you are not used to reading lambdas then here is the same code as above but with the lambdas made into local functions so the code reads a little more like english.

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

The second version is a little less tidy in my mind. In both of these examples you can see how the recursive approach lets you think about how to do just one step and then by calling itself you apply the solution for one step to get the solution to the entire problem

Answer 2

Just because your initial idea was to do this with loop. Here's how you might've done it:

(defun quicksort (list)
  (if (cdr list)
      (loop :with pivot := (car list)
         :for element :in list
         :if (< element pivot) :collect element :into a
         :else :if (= element pivot) :collect element :into b
         :else :collect element :into c
         :finally (return (nconc (quicksort a) b (quicksort c)))) list)) 

Answer 3

Barring compiler tricks, NTH takes O(i) time to access the ith element of a list, because it has to walk across every element of the list up to that point. This means that merely accessing every element of a list by using NTH will take O(n^2) time. Since quicksort is supposed to execute in O(nlgn) time, it is necessary to make a slight alteration.

By holding on to the remaining tail while you walk the list and accessing through that tail instead of using NTH, you can quicksort a list. It is also necessary to only walk the list in the forward direction because lisp lists are singly linked.

(defun simple-list-partition (list end)
  "Reorder list until end such that all values less than the first value in the
  list are placed left of it and all greater placed to its right; return the new
  index of the first value and the tail of the list starting with that value as
  multiple values."
  (loop for walk-cons on (cdr list)
        for walk-value = (car walk-cons)
        for walk-index from 1
        with pivot-value = (car list)
        with rotate-cons = list
        with rotate-index = 0
        while (<= walk-index end)
        when (< walk-value pivot-value)
        do (progn (setq rotate-cons (cdr rotate-cons)
                        rotate-index (+ 1 rotate-index))
                  (rotatef (car rotate-cons) (car walk-cons)))
        finally (progn (rotatef (car list) (car rotate-cons))
                       (return (values rotate-index rotate-cons)))))

(defun quicksort (list)
  "Quicksort for lists."
  (labels ((quicksort% (l  max)
             (when (and (plusp max) (cdr l))
               (multiple-value-bind (index tail)
                   (simple-list-partition l max)
                 (quicksort% l (1- index))
                 (quicksort% (cdr tail) (- max index 1))))))
    (quicksort% list (1- (length list)))
    list))

For simplicity the above doesn't protect against poor performance on lists that are either presorted or of equal elements.