Skip to content

Instantly share code, notes, and snippets.

@darrenldl
Created July 20, 2018 15:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save darrenldl/71a945bc32dcbe9dd14b2175ab767d81 to your computer and use it in GitHub Desktop.
Save darrenldl/71a945bc32dcbe9dd14b2175ab767d81 to your computer and use it in GitHub Desktop.
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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment