selection_sort.ml

open Utils

let imperative_sort a =
  let l = Array.length a in
  for i = 0 to (l - 1) do
    let min_idx = ref i in
    for j = i + 1 to (l - 1) do
      if (a.(j) < a.(!min_idx)) then min_idx := j
    done;

    if !min_idx != i then swap a i !min_idx
  done

let rec find_min ?(acc = []) = function
  | h1 :: h2 :: tl when h1 > h2 ->
    find_min ~acc:(h1 :: acc) (h2 :: tl)
  | h1 :: h2 :: tl ->
    find_min ~acc:(h2 :: acc) (h1 :: tl)
  | [x] -> (x, acc)
  | [] -> raise Not_found

let rec persistent_sort ?(acc = []) = function
  | [] -> List.rev acc
  | s ->
    let (min, rest) = find_min s in
    persistent_sort ~acc:(min :: acc) rest