selection_sort_fixed.ml

let swap (a : int array) (i : int) (j : int) : unit =
  let temp = a.(i) in
  a.(i) <- a.(j);
  a.(j) <- temp

(* Took a while to understand what you're trying to do in this function,
 * add comments in future whenever you have a non-trivial piece of code *)
let small_to_front (arr : int array) (start_unsorted : int) : unit =
  (* W.r.t aux, see below *)
  let rec aux (arr : int array) (start_unsorted : int) (i : int) (index_smallest : int) : unit =
    let last_index = (Array.length arr) - 1 in

    if i > last_index
    then (
      swap arr start_unsorted index_smallest
    )
    else (
      let index_smallest =
        if arr.(i) < arr.(index_smallest)
        then i
        else index_smallest
      in
      aux arr start_unsorted (i+1) index_smallest
    )
  in
  aux arr start_unsorted start_unsorted start_unsorted

let selection_sort (arr : int array) : unit =
  (* The following is an internal/nested function that does the actual processing
   *
   * The advantage here is that you can conceal the `i` from the external callers
   *
   * You can do similar things with optional arguments
   *
   * Outside of `aux`, you can also name it `selection_sort_helper`, `helper`, `go`,
   * or whatever really, but these are the common options.
   * Again, small things like this do not matter as long as you're consistent
   * throughout your project.
   *)
  let rec aux (arr : int array) (i : int) : unit =
    let last_index = (Array.length arr) - 1 in

    if i > last_index
    then ()
    else (
      small_to_front arr i;
      aux arr (i+1)
    )
  in
  aux arr 0

let print_arr (arr : int array) : unit =
  Printf.printf "[|";
  Array.iter (Printf.printf "%d, ") arr;
  Printf.printf "|]\n"

let () =
  let arr = [|3; 2; 1; 0|] in
  print_string "Raw :";
  print_arr arr;
  print_string "Sorted :";
  selection_sort arr;
  print_arr arr;