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;
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.
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
let rec f sorted = function
|  -> sorted
| a :: r -> f (insert  a sorted) r
f  l