CODEWITHSUNDEEP
lispcommon-lispquicksort
Shrp91
Shrp91

Reputation: 163

Quicksort in LISP

I am trying to do a quicksort using LISP but I am having trouble with my functions output. 

(defun qsort (L)
   (cond
   ((null L) nil)
   (t(append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or(null a)(null b) nil))
    (( < a (car b)) (list< a (cdr b)))
    (t(cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or( null a)(null b) nil))
    (( >= a (car b)) (list> a (cdr b)))
    (t(cons (car b) (list> a (cdr b))))))

My problem being when list< and list>= finish the list always ends with a .T. For instance:

> (list< '4 '(1 5 3 8 2))
Entering: LIST<, Argument list: (4 (1 5 3 8 2))
 Entering: LIST<, Argument list: (4 (5 3 8 2))
  Entering: LIST<, Argument list: (4 (3 8 2))
   Entering: LIST<, Argument list: (4 (8 2))
    Entering: LIST<, Argument list: (4 (2))
     Entering: LIST<, Argument list: (4 NIL)
     Exiting: LIST<, Value: T
    Exiting: LIST<, Value: (2 . T)
   Exiting: LIST<, Value: (2 . T)
  Exiting: LIST<, Value: (3 2 . T)
 Exiting: LIST<, Value: (3 2 . T)
Exiting: LIST<, Value: (1 3 2 . T)
(1 3 2 . T)

Why is (4 NIL) evaluating as T?

Upvotes: 3

Views: 11392

Answers (6)

Orm Finnendahl
Orm Finnendahl

Reputation: 208

I'd recommend to change the code of liya babu/Will Ness like this:

(defun quick (list)
  (if (null list) nil
      (let ((pivot (first list)) (less nil) (greater nil))
        (dolist (i (rest list))
          (if (< i pivot) (push i less) (push i greater)))
        (append (quick less) (list pivot) (quick greater)))))

Although just slightly edited I find it both more lispy and more succinct.

Upvotes: 1

brunocodutra
brunocodutra

Reputation: 2349

Your problem with list<, and also with list>=, lies on ((or ( null a)(null b) nil)), it should be (( or( null a)(null b)) nil). Note nil was moved outside of the condition to be the returned value.

Furthermore, on the definition of list>= you are calling list>, but I'm positive you meant list>= instead.

I would also suggest some indentation to address the legibility of lisp, like follows

(defun qsort (L)
  (cond
    ((null L) nil)
    (t
      (append
        (qsort (list< (car L) (cdr L)))
        (cons (car L) nil) 
        (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((< a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
  (cond
    ((or (null a) (null b)) nil)
    ((>= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))

Some testing follows:

(list< '4 '(1 5 3 8 2))
=> (1 3 2)

(list>= '4 '(1 5 3 8 2))
=> (5 8)

(qsort '(1 5 3 8 2))
=> (1 2 3 5 8)

Upvotes: 7

Constantin
Constantin

Reputation: 1

This should also work:

(defun qsort (l)
  (cond
   ((null l) nil)
   (t (append
       (qsort (car(list<> (car l)(cdr l))))
       (cons (car l) nil)
       (qsort (cadr(list<> (car l)(cdr l))))))))

(defun list<> (a b &optional rl rr)
    (cond
     ((null b) (list rl rr))
     ((<=(car b)a) (list<> a (cdr b) (cons (car b) rl) rr))
     (t (list<> a (cdr b)rl (cons (car b) rr)))))

(setq l (loop for j from 1 to 20 append (list(random 100))))
(qsort l)
;=> (86 99 9 31 66 58 57 43 48 21 51 0 32 69 39 47 59 76 69 23)
;=> (0 9 21 23 31 32 39 43 47 48 51 57 58 59 66 69 69 76 86 99)

Upvotes: -1

liya babu
liya babu

Reputation: 11

(defun quick (list)
  (when (< = (length list) 1) (return-from quick list))
  (let ((pivot (car list)) (rest (cdr list)) (less nil) (greater nil))
    (loop for i in rest do
      (if (< i pivot) (push i less) (push i greater)))
    (append (quick less) (list pivot) (quick greater))))

Upvotes: 1

rajappan
rajappan

Reputation: 1

There are some errors in the program. The corrected program is:

(defun qsort (L)
   (cond
   ((null L) nil)
   (t (append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or (null a) (null b)) nil)
    (( < a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or ( null a)(null b)) nil)
    (( >= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))

Upvotes: 0

chunyang.wen
chunyang.wen

Reputation: 242

Lisp has different kinds of collections. I think sort a list using quick-sort is not a good choice. In the implementation of STL in C++, the sorting method of list is merge-sort. I have tried to implement a 3-way quick-sort using the collections of array.

(defun quick-sort (arr start end)
  "Quick sort body"
  (if (< start end)
  (let ((n-pair (partition arr start end)))
  (quick-sort arr start (car n-pair))
  (quick-sort arr (cdr n-pair) end))
))

(defun partition (arr start end)
 "Partition according to pivot."
 (let ((pivot (aref arr start)) (cur start))
 (loop while (<= start end) do
  (cond
    ((< pivot (aref arr start)) ; pivot < arr[start], swap with arr[end]
     (swap arr start end) (decf end))
    ((> pivot (aref arr start)) ; pivot > arr[start], swap with arr[start]
     (swap arr cur start) (incf cur) (incf start))
    (t                          ; otherwise
     (incf start))))
    (cons (decf cur) start)))

(defun swap (arr i j)
 "Swap element of arr"
 (let ((tmp (aref arr i)))
 (setf (aref arr i) (aref arr j))
 (setf (aref arr j) tmp)))

Upvotes: 1

Related Questions