Hello everyone,
I'm sorry if my request is naive and annoying but I need to find the
QuickSort Algorithm in LISP.
My email is ·········@hol.gr
Thank you in advance
Tassos Tsotsoros
On Mon, 9 Jun 1997 18:59:09 +0300, "TassosT" <·········@hol.gr> wrote:
>I'm sorry if my request is naive and annoying but I need to find the
>QuickSort Algorithm in LISP.
This one is for AutoLISP and therefore very inefficient,
but maybe it's of interest.
(defun qsort (lst cmp / x y l e g)
(if lst
(progn
(setq x (nth (/ (length lst) 2) lst))
(foreach y lst
(cond
((equal y x)
(setq e (cons y e)))
((apply cmp (list y x))
(setq l (cons y l)))
(T (setq g (cons y g)))
)
)
(append (qsort l cmp) e (qsort g cmp))
)
)
)
--
Reini
AutoCAD stuff: http://xarch.tu-graz.ac.at/autocad/
"TassosT" <·········@hol.gr> writes:
>
> Hello everyone,
>
> I'm sorry if my request is naive and annoying but I need to find the
> QuickSort Algorithm in LISP.
>
> My email is ·········@hol.gr
>
> Thank you in advance
>
> Tassos Tsotsoros
>
>
>
How about this one. Note that QuickSort may not be the best way to
sort lists, since you end up having to do a bunch of appends. qsort
was really designed to take advantage of being able to sort in place.
(defun qsort (lst)
"qsort for lists."
(labels ((partition (left right acc)
(if (null acc)
(append (qsort left)
(cons (car lst) (qsort right)))
(if (<= (first acc) (first lst))
(partition (cons (first acc) left) right (rest acc))
(partition left (cons (first acc) right) (rest acc))))))
(if (null (rest lst))
lst
(partition nil nil (rest lst)))))
--
Adam P. Jenkins
···············@cs.umass.edu