(* Corrigé d'Introduction à la programmation *)
(* Exercices sur le tri des listes et les opérations en queue de liste *)
(* Ancien TP4 *)

(* --------------------------------------------------------- *)

(* Le dernier élément d'une liste *)

let rec dernier  = function
      []   -> failwith "dernier"
    | [a]  -> a
    | t::r -> dernier r ;;

(* Ajouter un élément en queue de liste *)

let rec ajoutqueue x = function
      []   -> [x]
    | t::r -> t::ajoutqueue x r;;

(* Supprimer un élément en queue de liste *)

let rec supqueue  = function
	[]   -> []
      | [a]  -> []
      | t::r -> t::supqueue r ;;

(* --------------------------------------------------------- *)

(* La lecture d'une liste au clavier *)

let rec lit_liste = function
    0 -> []
   |n -> read_int()::lit_liste (n-1);;

(* les deux fonctions suivantes viennent du TD7 *)

let rec concat l1 l2 =
  match (l1,l2) with
        ([],l2) -> l2
        |(x::r1,l2) -> x::concat r1 l2;;

let rec Renverser = function
  [] -> []
 |x::r -> concat (Renverser r) [x];;
 
let rec liste_lit = function n -> Renverser (lit_liste n);;

(* --------------------------------------------------------- *)

(* Le lancer de $m$ dés à $n$ faces *)

let LancerUnDeANFaces n = 1 + random__int n;;

let rec LancerMDeANFaces n = function
 0 -> []
|m -> (LancerUnDeANFaces n) :: (LancerMDeANFaces n (m-1));;


(* --------------------------------------------------------- *)

(* Le tri par recherche de minimum *)

(* Écrire une fonction qui, étant donnée une liste d'entiers, *)
(* renvoie le plus petit élément de cette liste. *)

let rec lepluspetit = function
       []   -> failwith "lepluspetit"
     | [a]  -> a
     | t::r -> let pt = lepluspetit r in 
                   if t < pt then t else pt;;

(* En utilisant la fonction précédente, écrire une fonction qui, *)
(* étant donnée une liste d'entiers, renvoie une autre liste,    *)
(* mais dont les éléments ont été rangés dans l'ordre croissant. *)

(* la fonction suivante vient du TD9 *)
let rec suppr x= function
  [] -> []
 |t::r -> if x=t then r else t::(suppr x r);;

let rec trisimple = function
      []   -> []
    | l    -> let pt = lepluspetit l in
                  pt::trisimple(suppr pt l);;

(* --------------------------------------------------------- *)

(* Le tri par insertion *)

(* Écrire une fonction qui, étant donnée une liste $l$ dont les    *)
(* éléments sont triés dans l'ordre croissant, et d'un élément $x$ *)
(* renvoie une liste contenant les éléments de la liste $l$ et $x$ *)
(* triés dans l'ordre croissant. *)

let rec insertion x l = match l with 
  []   -> [x]
| t::r -> if x<t then x::l else t::(insertion x r);;

 
(* insertion 2  [0; 0; 5; 7; 9; 86; 89; 97] ;; *)
(* - : int list = [0; 0; 2; 5; 7; 9; 86; 89; 97]  *)

(* Le tri d'une liste *)

(* En utilisant la fonction précédente, écrire une fonction qui, *)
(* étant donnée une liste d'entiers, renvoie une autre liste,    *)
(* mais dont les éléments ont été rangés dans l'ordre croissant. *)
 
let rec tri_insertion l = match l with 
  []   -> []
| t::r -> insertion t (tri_insertion r);;

(*  tri_insertion [0;9;7;0;97;89;86;5];;*)
(* - : int list = [0; 0; 5; 7; 9; 86; 89; 97] *)



(* --------------------------------------------------------- *)
(* Quelques algorithmes de tri en CAML *)

(* ------ le tri par insertion ----- *)

let triinsertion inferieur l = 
 (* insere un élément dans une liste triée *)
 let rec insertion e = function
   [] -> [e]
  |t::q -> if inferieur e t then e::t::q else t::insertion e q
 in
  (* effectue les insertions *)
  let rec aux l = function 
    [] -> l
   |t::q -> aux (insertion t l) q
  in aux [] l;;

(* ----- le tri par fusion ----- *)

let rec trifusion inferieur = function
  [] -> []
 |[a] -> [a]
 |l -> 
  (* la fonction de fusion de deux listes triees *)
  let rec merge l1 l2 = 
   match (l1,l2) with
     ([],[]) -> []
    |(l,[]) -> l
    |([],l) -> l
    |(a::li,b::lo) ->
     if inferieur a b then a::merge li (b::lo)
     else b::merge (a::li) lo
  (* separe une liste en deux listes de tailles egales *)
  and split = function
    [] -> ([],[])
   |[a] -> ([a],[])
   |a::b::l -> let (l1,l2) = split l in (a::l1,b::l2)
  in let (l1,l2) = split l in merge (trifusion inferieur l1) (trifusion inferieur l2);;

(* ----- tri par minimum ----- *)

let rec triminimum inferieur = function
  [] -> []
 |l -> 
  (* separe une liste en son element minimal et la liste privee de cet element *)
  let minl = function
    a::l ->
     let rec minlaux li a = function
       [] -> (a,li)
      |b::ls ->
        if (inferieur a b) then minlaux (b::li) a ls
        else minlaux (a::li) b ls
     in minlaux [] a l
   |_ -> failwith("Erreur impossible !")
  in let (a,li) = minl l in a::triminimum inferieur li;;

(* ------- le tri bulle ------- *)

let rec tribulle inferieur l = 
 (* teste si une liste est triée *)
 let rec est_triee = function
   a::b::l -> (inferieur a b) & (est_triee [b::l]) 
  |_ -> true
 (* effectue un parcours/echange *)
 and echange = function
   a::b::l -> if inferieur a b then a::echange (b::l) else b::echange (a::l)   
  |l -> l
 in if est_triee l then l else tribulle inferieur (echange l);;