(**********************************************)
(* Quelques tris décrits de façon récursive *)
(**********************************************)
(* I *)
(** Tri par insertion **)
(* insertion d'un élément x dans une liste triée *)
let rec insertion x liste = match liste with
| [] -> [x]
| t::q -> if t>x
then x::liste
else t::(insertion x q)
;;
(* on insère la tête dans la liste triée... *)
let rec tri_insertion liste = match liste with
| [] -> []
| t::q -> insertion t (tri_insertion q)
;;
tri_insertion [1; 3; 5; 4; 8; 6; 0];;
(* - : int list = [0; 1; 3; 4; 5; 6; 8] *)
(* II *)
(** Tri pivot **)
(* On choisit un élément de la liste (le premier),
* on sépare le reste en deux listes : la liste des éléments
* inférieurs et la liste des éléments supérieurs. Ensuite,
* on appelle le tri sur chacune de ces listes récursivement
* et on retourne
* liste1_triée @ pivot::liste2_triée
*)
let rec separe_aux pivot liste linf lsup = match liste with
| [] -> linf, lsup
| t::q -> if t>pivot
then
separe_aux pivot q linf (t::lsup)
else
separe_aux pivot q (t::linf) lsup
;;
let rec tri_pivot liste = match liste with
| [] -> []
| pivot::q -> let (linf, lsup) = (separe_aux pivot q [] []) in
(tri_pivot linf) @ (pivot::(tri_pivot lsup))
;;
tri_pivot [1; 3; 5; 4; 8; 6; 0];;
(* - : int list = [0; 1; 3; 4; 5; 6; 8] *)
(* III *)
(** Tri à l'aide d'arbres binaires de recherche **)
(* Cela consiste à insérer tous les éléments dans
* un arbre binaire puis à effectuer un parcours
* infixe de l'arbre. *)
(* On reprend le type arbre *)
type arbre = Lambda | Noeud of int * arbre * arbre;;
(* inserer dans un arbre binaire de recherche *)
let rec inserer x arbre = match arbre with
| Lambda -> Noeud(x, Lambda, Lambda)
| Noeud(a, g, d) -> if a<x
then Noeud(a, g, inserer x d)
else Noeud(a, inserer x g, d)
;;
(* parcours infixe de l'arbre :
* arbre gauche
* noeud
* arbre droit *)
let rec infixe arbre = match arbre with
| Lambda -> []
| Noeud(x, g, d) -> (infixe g) @ (x::(infixe d))
;;
let rec creer_abr liste = match liste with
| [] -> Lambda
| t::q -> inserer t (creer_abr q)
;;
let tri_abr liste = infixe (creer_abr liste);;
tri_abr [1; 3; 5; 4; 8; 6; 0];;
(* - : int list = [0; 1; 3; 4; 5; 6; 8] *)