I have screwed something up in my selection sort

Learning
7

Some feedback:

  1. Function definitions are different in OCaml(and most other functional programming languages) compared to some of the more commonly used languages, specifically commas mean tuple in OCaml.
    For example,
(* this has a type signature of int -> int -> int*)
let f x y = x + y;;

(* while this has a type signature of int * int -> int *)
let f' (x, y) = x + y;;

let x = (1, 2, 3);; (* this has type signature of int * int * int *)

In f, you have a function that takes two separate arguments.
In f', which is what you wrote, you had a function that takes a single argument of a tuple type, and you pattern match x, y to the tuple argument.

  1. In general, people add type annotations/signatures to make code self-documenting to some extent

  2. Naming convention. AFAIK people tend to go with underscores in OCaml code, though in practice as long as your project is consistent with a certain style, no one complains really.

  3. Make your names more descriptive.

  4. Arrays in OCaml know their lengths, and you can retrieve the length in O(1), so you don’t need to pass the last index around in all function calls.

  5. Always add begin .. end or () when you put multiple statements in the else clause. When you have a if ... then ... else expr1; expr2, only expr1 belongs in the else part, else2 will always be executed.

Here’s a version that’s polished according to above points, but not completely fixed:

let swap (a : int array) (i : int) (j : int) =
  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 rec small_to_front (arr : int array) (start_unsorted : int) (i : int) (index_smallest : int) =
  let last_index = (Array.length arr) - 1 in
  if i > last_index
  then swap arr start_unsorted index_smallest
  else (
    if arr.(index_smallest) < arr.(start_unsorted)
    then small_to_front arr start_unsorted (i+1) index_smallest
    else small_to_front arr start_unsorted (i+1) index_smallest
  )

let rec selection_sort (arr : int array) (i : int) =
  let last_index = (Array.length arr) - 1 in
  if i > last_index
  then ()
  else (small_to_front arr i i i; selection_sort arr (i+1))

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
  selection_sort arr 0;
  print_string "Raw :";
  print_arr arr;
  print_string "Sorted :";
  selection_sort arr 0;
  print_arr arr;

Please give it a shot at fixing above code before looking at the fixed version.

My fixed and slightly improved version as gist

=====

IMO it is in your best interest to apologise to @perry in some way, if you have not done so already. I absolutely don’t think perry’s response warranted any harshness. But obviously what you decide to do is beyond my control.