How to create insertion sort in ocaml?

Learning
1

How would you write insertion sort in ocaml style?

Example from c beneath.
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;

   /* Move elements of arr[0..i-1], that are
      greater than key, to one position ahead
      of their current position */
   while (j >= 0 && arr[j] > key)
   {
       arr[j+1] = arr[j];
       j = j-1;
   }
   arr[j+1] = key;

}
}

2

Although it isn’t ideal, you can duplicate your C algorithm in OCaml. OCaml has mutable arrays, for loops, and all the rest. You can also do insertion sort in a more functional style.

If this is a homework assignment for you, I suggest that you work on it a while on your own, it will probably teach you more that way.

3

Hi, I don’t know whether it’s a good idea to provide a solution, I hope you will have searched by yourself before looking at this message. I am a beginner too, so I might have written something not so efficient, but that’s a solution I found without imperative features, if you want to practice your functional style !

I am using the insert sub-function to insert a new element at the right place in a list, using an accumulator for tail-recursion optimisation. The f sub-function processes the list and inserts each element in a sorted accumulator that I am keeping in the calls in order to use recursion efficiently.

let insertion_sort l =
  let rec insert acc e = function
    | [] -> List.rev_append acc [e]
    | a :: r ->
      if e < a then List.rev_append acc (e :: a :: r)
      else insert (a :: acc) e r
  in
  let rec f sorted = function
    | [] -> sorted
    | a :: r -> f (insert [] a sorted) r
  in
  f [] l
1 Like