Can anyone help me with this simple insertion sort program. I am using
release 3 of XLISP-STAT as my lisp compiler. Here is the pseudocode of
the program. If anyone can e-mail me the code in lisp, I would very much
appreciate it. I am particularly having trouble referring to elements
in the array A[j] and setting up an array. Basically, I would like to
see all the code since I am new to the lisp programming language. Here
is the pseudocode....
INSERTION-SORT(A)
for j = 2 to length(A)
do key = A[j]
//Insert A[j] into the sorted sequence A[1..j-1]
i = j - 1
while i>0 and A[i]>key
do A[i+1]=A[i] //make a place
i=i-1
A[i+1]=key //insertion
That's it. It is probably simple to alot of you LISP experts. The
symbols "//" basically start a comment and are not actual code. If anyone
can help me with this problem including setting up any variables or arrays
that I might need them, please e-mail me at as soon as possible....
········@UMASSD.EDU
In article <··········@gatekeeper.umassd.edu>, ········@umassd.edu wrote:
> Can anyone help me with this simple insertion sort program. I am using
> release 3 of XLISP-STAT as my lisp compiler. Here is the pseudocode of
> the program. If anyone can e-mail me the code in lisp, I would very much
> appreciate it. I am particularly having trouble referring to elements
> in the array A[j] and setting up an array. Basically, I would like to
> see all the code since I am new to the lisp programming language. Here
> is the pseudocode....
>
> INSERTION-SORT(A)
> for j = 2 to length(A)
> do key = A[j]
> //Insert A[j] into the sorted sequence A[1..j-1]
> i = j - 1
> while i>0 and A[i]>key
> do A[i+1]=A[i] //make a place
> i=i-1
> A[i+1]=key //insertion
something like:
(defun insertion (array)
(let (v j)
(do ((i 1 (1+ i)))
((>= i (length array)) array)
(setf v (aref array i)
j i)
(do ()
((not (and (> j 0) (> (aref array (1- j)) v))))
(setf (aref array j) (aref array (1- j)))
(decf j))
(setf (aref array j) v))))
(insertion #(5 3 6 7))
Or CL's LOOP syntax
(defun insertion (array)
(loop for i from 1 below (length array)
for v = (aref array i)
for j = i
do (loop while (and (> j 0)
(> (aref array (1- j)) v))
do (setf (aref array j) (aref array (1- j)))
do (decf j))
do (setf (aref array j) v))
array)
You also may want to have predicate and key parameters.
--
http://www.lavielle.com/~joswig/