(**********************************************)
(*  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] *)