I wrote the following code for quicksort pretty much similar to the C code. But here it only reads elements to the list.after that it says that the partition function should be a lambda function.I' m new to lisp. Please help me.My code is:-
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)
)
(defun quicksort(start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end))))
)
(defun partition(start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j)
)
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp)
)
(quicksort 0 10)
And want to know whats this lambda function.whether it's just an anonymous name given to a function that is not yet defined
I'll do this step by step. First, use standard formatting:
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
Put out the current problem: parentheses always surround forms, they do not group forms by themselves.
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
Some errors, line by line:
(print "Enter the elements of the array")
(setq k 10) ; warning: no variable K
(setq A (make-array '(10))) ; warning: no variable A
(setq i 0) ; warning: no variable I
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)) ; warning: k never used
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end))) ; this lambda always returns nil
(quicksort (start (- pindex 1))) ; START is not a function
(quicksort ((+ pindex 1) end))))) ; (+ PINDEX 1) is not a function
(defun partition (start end)
(setq pivot (aref A end)) ; warning: no variable PIVOT
(setq pindex start) ; warning: no variable PINDEX
(setq j 0) ; warning: no variable J
(loop
(if (>= j end) return) ; warning: no variable RETURN
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex)) ; warning: no variable TEMP
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
Get rid of the "no variable" warnings. Setq does not introduce variables.
Most Common Lisp implementations do something useful so that this seems to work,
but it is undefined behaviour. You could declare these variables globally
special with defvar or defparameter, but what you actually need here is a
function to read user input inside which you can use let to make local
bindings. It also returns the read array instead of setting global state. I
also chose to use K as a parameter for some flexibility of use. Finish-output
ensures that the prompt is displayed before the first number is to be entered.
(defun read-integers (k)
(print "Enter the elements of the array.")
(finish-output)
(let ((a (make-array (list k)))
(i 0))
(loop
(if (>= i k)
(return))
(let ((x (read)))
(setf (aref a i) x)
(incf i)))
a))
This still leaves much room for improvement, but at least it works.
Next: repair quicksort. Since it does not use partition anywhere but sports
an empty lambda form, I assume that you wanted to call partition there. I
also repair the calling forms and missing binding:
(defun quicksort (start end)
(if (< start end)
(let ((pindex (partition start end)))
(quicksort start (- pindex 1))
(quicksort (+ pindex 1) end))))
This operates on a global array that you do not see mentioned anywhere in its
body. This is very confusing and makes the code very unreadable and
unmaintainable. It is much better to give the array as a parameter, so that you
call it as (quicksort (read-integers 10) 0 10).
For performance, we need to operate on it in place, which is unusual enough that it ought to be mentioned in the docstring. I return the array so that the usual semantics of sort can be used for it. An IF without alternative clause is better written as a WHEN.
(defun quicksort (array start end)
"Destructively sorts ARRAY in place."
(when (< start end)
(let ((pindex (partition array start end)))
(quicksort array start (- pindex 1))
(quicksort array (+ pindex 1) end)))
array)
This still contains an off-by-one error, but I'll look at partition now.
First, address the usual binding problems:
(defun partition (array start end)
"Chooses an arbitrary pivot element from array between START and END, then
destructively partitions the elements of ARRAY between START and END
in-place into those smaller than the pivot, then the pivot, then those
bigger than the pivot. Finally returns the index of the pivot."
;; FIXME: doesn't work
(let ((pivot (aref array end))
(pindex start)
(j 0))
(loop
(if (>= j end) (return))
(if (< (aref array j) pivot)
(let ((temp (aref array pindex)))
(setf pindex (aref array j))
(setf (aref array j) temp)
(incf pindex)))
(incf j))
(let ((temp (aref array pindex)))
(setf (aref array pindex) pivot)
(setf (aref array end) temp))))
This is just wrong. Please look up how quicksort works.
Hints:
rotatefposition-if might be useful. Look it up in the Hyperspec.partition by itself. When it works, fix quicksort.