Insertion Sort

Its been a while since I posted any Lisp content and I have not been in touch for long. For anyone trying to get in touch, I still don't have access to my Yahoo account.

Well, I was trying a simple insertion sort algorithm directly from a book.

(defun insertion-sort (A)
  (do ((j 1 (+ j 1)))
      ((>= j (length A)) 'done)
    (let ((key (aref A j))
          (i (- j 1)))
      (while (and (>= i 0) (> (aref A i) key))
        (progn
          (setf (aref A (+ i 1)) (aref A i))
          (setf i (- i 1))
          (setf (aref A (+ i 1)) key)
          (print x))))))

The while is just a macro copied out of ANSI Common Lisp and very basic (no gensyms etc). Just for reference, it is

(defmacro while (test &rest body)
  `(do ()
    ((not ,test))
    ,@body))

Executing it as follows (Followed the algo by the book).

CL-USER> x
#(5 2 4 6 1 3)
CL-USER> (insertion-sort x)

#(2 5 4 6 1 3)
#(2 4 5 6 1 3)
#(2 4 5 1 6 3)
#(2 4 1 5 6 3)
#(2 1 4 5 6 3)
#(1 2 4 5 6 3)
#(1 2 4 5 3 6)
#(1 2 4 3 5 6)
#(1 2 3 4 5 6)
DONE
CL-USER> x
#(1 2 3 4 5 6)

Its amazing, how much one forgets in a few months/years.