Bubble sort (Lisp)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

Here's an implementation of bubble sort with Common Lisp

Implementation

(defun bubble-sort (array cmp-fun) 
  "Bubble sort implementation in common lisp. Using the extended loop facility."
  (let ((result (copy-seq array)))
    (loop for i from (1- (length result)) downto 0 do
        (loop for j from 0 to i
            when (funcall cmp-fun (aref result i) (aref result j))
               do (rotatef (aref result i) (aref result j)) ))
    result))

It's quite generic, you just have to provide the proper cmp-fun. The implementation uses the extended loop facility. You can see it as a small sub-language embedded into Common Lisp.

Because I like to have a somewhat clean sort function, I did not change the parameter but created a new array as result.

The macro rotatef comes in handy here, one can use it as a "built-in" swap function as here.

In Common Lisp the array index starts at zero as it does e.g in C.

Note: The Common Lisp specified loop is destructive.

Usage example

You can use the REPL for trying the sort function Here for an array of integers:

(bubble-sort #(1 -1 2 -10) #'<)
#(-10 -1 1 2)

or with strings:

(bubble-sort #("one" "two" "three") #'string<)
#("one" "three" "two")

Of course you can use it for self defined classes also. One could e.g implement the same interface as the normal sort function.