1

for my study I need to explain the function of Quicksort programmed in Common Lisp. I am honest, I really don't know how to work with Common Lisp. I got a code from the internet (for my professer it is okay to use the code from the internet) which solves the problem of sorting a list of numbers.

I really don't understand this code, can somebody please explain it to me, what it exacly does?

Thanks so far!! 

(defun quick-sort (list)
  (if (cdr list)
    (let ((pivot (car list)))
      (flet ((filter (operator)
               (remove-if-not
                 (lambda (n) (funcall operator n pivot))
                 list)))
        (append (quick-sort (filter #'<))
                (filter #'=)
                (quick-sort (filter #'>)))))
    list))
Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
Marvin Huetter
  • 19
  • 1
  • Did you read the description of the Quicksort algorithm, for example on Wikipedia https://en.wikipedia.org/wiki/Quicksort ? – Rainer Joswig Jun 01 '19 at 15:42
  • do you mean you don't know Lisp at all? how its code is structured, what is define, let, append, flet, if, remove-if-not, lambda? – Will Ness Jun 01 '19 at 15:47
  • 5
    If you understand the quicksort algorithm it is straight forward to read the Common Lisp code even with meager knowledge of any lisp dialect. If you don't understand the algorithm or language you should read up before asking. Note that this is [not quicksort but a deforested tree sort](https://stackoverflow.com/questions/11355621/pseudo-quicksort-time-complexity) since it lacks in place partitioning. – Sylwester Jun 01 '19 at 16:12
  • I am not sure how to extend a question without giving an answer but how could this piece of code be extended to use a general predicate `&key (pred #'<)` given by the user? Simply substitute `#'<` with the key variable `pred` and `#'>` with `(complement pred)` (and `#'=` with `#'equal`) lead to an infinite recursion. – Martin Buchmann Jun 03 '19 at 12:26

0 Answers0