Insertion sort (Lisp)

From LiteratePrograms

Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

Welcome to a round of Common Lisp. The following is an implementation of insertion sort with Common Lisp. Common Lisp is a programming language which supports all kind of programming, among others:

• imperative programming (comparable to C, Pascal)
• functional programming
• object oriented programming (with a unique approach to object-orientation)

Implementation - Insertion sort (Lisp)

The following is a slighly rewrite from Insertion sort (C) and Insertion sort (OCaml)

(defun insertion-sort (cmp-fun array-to-sort) 
  "Implementation of a destructive insertion sort on ARRAY-TO-SORT.
The CMP-FUN is used to parametrize the order conditions. 
This sort is generic, that means it can sort all kinds of objects for which
one can run the CMP-FUN"
  (flet ((insert-into-sorted (index)
           ;; example of a local function all outer variables are 
           ;; accessible from within this local function
           (let ((el (aref array-to-sort index)))
             ;; save the element for later insertion
             (loop for j = (1- index) then (1- j)
                   while (and (>= j 0) (not (funcall cmp-fun (aref array-to-sort j) el)))
                   ;; the not is needed because the following should move all elements
                   ;; not in order to the right
                   do (setf (aref array-to-sort (1+ j)) (aref array-to-sort j))
                   finally  (setf (aref array-to-sort (1+ j)) el)))))
                   ;; now we can add el at the proper place
    (loop for i from 0 upto (1- (length array-to-sort))
          do (insert-into-sorted i)))
  array-to-sort)
;; I do return the parameter because that's the way things 
;; are done with Common Lisp

Nothing really special in this implementation but the use of a local function which is responsible for insertion at the proper place.

The whole starts in the second form starting with (loop for i . I used the extended loop facility of Lisp here, however you could have go with a norm do or dotimes loop.

The other somewhat more difficult to understand part is the (not (funcall cmp-fun ... piece. One can treat functions as first class citizens in Common Lisp, however function names life in their own namespaces. So I could have a variable names cmp-fun and a function with the same name. In this case I explicitly to a funcall on the symbol with the name cmp-fun. And there for the function cell is called.

The not is needed because I move away all element no matching the proper order.

Testing is quite easy just write the following in the REPL

(insertion-sort #'< #(1 -1 2 -2 -3))

1. (-3 -2 -1 1 2)

Or if you like to sort some string you can do a

(insertion-sort #'string< #("aka" "foo" "bar"))

1. ("aka" "bar" "foo")

So this function is generic it can everything, you just have to define a cmp-fun which takes care of the comparison.

Here's an example using a self defined class:

(defclass t1 ()
              ((i-val :accessor i-val :initarg :i-val)
               (s-val :accessor s-val :initarg :s-val)))

with the following comparison-function

(defmethod t1-cmp-fun ((v1 t1) (v2 t1))
              (< (i-val v1) (i-val v2)))

and an a decent overwritten printing function:

 (defmethod print-object ((obj t1) stream)
                   (format stream "i-val = ~a, s-val = ~a~%" (i-val obj) (s-val obj)))

We can run our insertion sort like this:

(insertion-sort #'t1-cmp-fun `#( ,(make-instance 't1 :i-val 1 :s-val "one")
                                           ,(make-instance 't1 :i-val 2 :s-val "two")))

and get:

#(i-val = 1, s-val = one
 i-val = 2, s-val = two
)

Which is quite ok.

What one really does

Of course hardly anyone would implement insertion sort with Common Lisp, because it has standard functions for sorting. So in the end one would write: (sort #(1 -1 2 -2 -3) #'<)

1. (-3 -2 -1 1 2)

and be done with it. Even the sorting of the self defined class could be done with this sort routine

(sort  `#( ,(make-instance 't1 :i-val 1 :s-val "one")
           ,(make-instance 't1 :i-val 2 :s-val "two"))
        #'< :key #'i-val)   

output:

#(i-val = 1, s-val = one
 i-val = 2, s-val = two
)

I suggest you jump over your shadow and give Common Lisp a go. It's a quite different but also very interesting language.

Download code