59 lines
1.1 KiB
OCaml
59 lines
1.1 KiB
OCaml
(* Exercice 1 *)
|
|
(* Insertion sort *)
|
|
let rec insert l x = match l with
|
|
| [] -> [x]
|
|
| y::t -> if x <= y then x::l else y::(insert t x)
|
|
;;
|
|
|
|
let insertion_sort l =
|
|
List.fold_left
|
|
(fun acc x -> insert acc x)
|
|
[]
|
|
l
|
|
;;
|
|
|
|
(* Selection sort *)
|
|
let rec min_l l = match l with
|
|
| [] -> invalid_arg "Empty list"
|
|
| [x] -> x, []
|
|
| x::q ->
|
|
let y, qy = min_l q in
|
|
if x < y then x, q else y, (x::qy)
|
|
;;
|
|
|
|
let rec selection_sort l = match l with
|
|
| [] | _::[] -> l
|
|
| _ ->
|
|
let m, q = min_l l in
|
|
m::(selection_sort q)
|
|
;;
|
|
|
|
(* Exercice 3 *)
|
|
let rec split l n =
|
|
if n = 0 then [], l
|
|
else match l with
|
|
| [] -> failwith "Splitting empty list"
|
|
| a::q ->
|
|
let qa, lb = split q (n-1) in
|
|
a::qa, lb
|
|
;;
|
|
|
|
let rec fuse la lb = match la, lb with
|
|
| [], _ -> lb
|
|
| _, [] -> la
|
|
| a::qa, b::qb ->
|
|
if a > b then
|
|
b::(fuse la qb)
|
|
else
|
|
a::(fuse qa lb)
|
|
;;
|
|
|
|
let rec fusion_sort l =
|
|
let n = List.length l in
|
|
if n <= 1 then l else
|
|
let la, lb = split l (n/2) in
|
|
let sa = fusion_sort la in
|
|
let sb = fusion_sort lb in
|
|
fuse sa sb
|
|
;;
|