Insertion sort (OCaml)

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

This is a simple example of the insertion sort sorting algorithm, written in OCaml. OCaml offers both mutable and immutable data-structures, so we will show an imperative implementation to sort an array in-place and a functional implementation to sort a list.

We will sort the data of type 'a with a "greater than" function ( >: ) : 'a -> 'a -> bool (this makes use of the fact that OCaml can define new infix operators).

Contents 1 Sorting in place 1.1 Implementation 1.2 Testing 2 Sorting immutable lists 2.1 Implementation 2.2 Testing

Sorting in place

Implementation

When sorting an array with insertion sort, we conceptually separate it into two parts:

• The array of elements already inserted, which is always in sorted order and is found at the beginning of the array;
• The array of elements we have yet to insert, following.

In outline, our primary function looks like this:

<<insertion_sort_mutable.ml>>=
let insertion_sort ( >: ) a =
  for i=0 to Array.length a - 1 do
    insert a.(i) into sorted sublist
  done

Here, the index i represents both the index of the next element to insert and the length of the sorted sublist constructed so far.

To insert each element, we need to create a hole in the array at the place where the element belongs, then place the element in that hole. We can combine the creation of the hole with the searching for the place by starting at the end and shifting each element up by one until we find the place where the element belongs. This overwrites the element we're inserting, so we have to save it in a variable first:

<<insert a.(i) into sorted sublist>>=
(* Insert a.(i) into the sorted sublist *)
let v = a.(i)
and j = ref(i - 1) in
while !j >= 0 && a.(!j) >: v do
  a.(!j + 1) <- a.(!j);
  decr j
done;
a.(!j + 1) <- v;

You must be aware that the average and worse case time complexity of insertion_sort a are O(N²) where N = Array.length a hence it is not recommended in practice (use a O(NlogN) algorithm instead).

Testing

There are several ways to compile ocaml code (either to bytecode or native code) but for testing we recommend you to use the interactive toplevel ocaml (the # is the prompt and start the lines you type in, the other lines are the answers of the system):

# let a = [|5; 3; 1|];;
val a : int array = [|5; 3; 1|]
# insertion_sort (>) a;;
- : unit = ()
# a;;
- : int array = [|1; 3; 5|]

Sorting immutable lists

Implementation

As above, we will make a function insertion_sort : ('a -> 'a -> bool) -> 'a list -> 'a list that will take a "greater than" comparison function >: and a list and return the list sorted.

The function is recursive (hence the rec keyword) and distinguish different kind of lists (hence the function):

<<insertion_sort_immutable.ml>>=
let rec insertion_sort ( >: ) = function

The empty list [] is already sorted:

<<insertion_sort_immutable.ml>>=
  | [] -> []

If the list is not empty it consists of a first element x followed by the remaining part of the list tl (for tail). We sort tl and insert x at the right place:

<<insertion_sort_immutable.ml>>=
  | x :: tl -> insert ( >: ) x (insertion_sort ( >: ) tl)

It remains to write insert. Again, this is done by recursing on the list. Inserting an element x into the empty list is easy:

<<insertion_sort_immutable.ml>>=
and insert ( >: ) x = function
  | [] -> [x]

If the list is made of a first element y and a tail tl, one has to check whether x is greater than y. In this case is must be inserted later in the list. Otherwise, it is the first element of the new list.

<<insertion_sort_immutable.ml>>=
  | y :: tl when x >: y -> y :: (insert ( >: ) x tl)
  | l -> x :: l

Testing

As before we use the toplevel to interactively test our code:

# insertion_sort (>) [5; 3; 1 ];;
- : int list = [1; 3; 5]
# insertion_sort (>) ["bob"; "alice"; "zoe"; "barry"];;
- : string list = ["alice"; "barry"; "bob"; "zoe"]

Download code