TD3 - Preparation

(* TD n°3 : Nombre d'inversion dans une permutation ou une liste*)

(* Vocabulaire :
- permutation = application bijective de (1,...n) dans (1,...,n)
- une liste est associée à une permutation si, après tri, elle devient [1;2;...;n]
- le i-ème élément d'une telle liste est "o(i)" (à 2 on associe o(2), à i on associe o(i) )
- on appelle inversion un couple (i,j) tel que i < j et o(i) > o(j) *)

(* Exercice 1 :
1. Pour compter le nombre d'inversions dans une liste associée à une permutation, on peut parcourir tous les couples (i,j) possibles avec i < j, et compter à chaque fois qu'on a o(i) > o(j).

2. En comptant que la complexité est la vérification " o(i) > o(j) ", la complexité équivaut aux nombres de couples possibles (i,j) avec i < j.
for j=0 to (n-1) do
for i=0 to j do
qui en calculant équivaut à n + (n*(n-1))/2 = (n² + n)/2 = O(n²)

3. *)

List.nth [1;2] 2;;

let calcul_inversion sigma =
let n = List.length sigma in
let compteur= ref 0 in
for j=0 to n-1 do
    for i=0 to j do
        if (List.nth sigma i) > (List.nth sigma j) then incr compteur;
        done;
        done;
        !compteur;;

calcul_inversion [1;2;3;4;5;6];;
calcul_inversion [1; 3;2 ;4;5;6];;
calcul_inversion [1;3;2 ;5;4 ;6];;
calcul_inversion [1;3; 5;2 ;4;6];;


(* Exercice 2
1. Dans l'algorithme de tri par fusion, on divise en deux les listes jusqu'à obtenir des singletons. A partir des singletons, on doit faire une comparaison pour les remettre dans l'ordre, puis à nouveau jusqu'à récupérer la liste de la même longueur.
Lors de ces comparaisons, on ajoute 1 au compteur pour chaque "permutation" à faire (lorsqu'ils ne sont pas dans le bon ordre)

2. La complexité du tri par fusion est en n*log(n). En l'adaptant, on ne rajoute que des additions car les comparaisons y sont déjà. On ne modifie pas la complexité (multiplication par 2 qui ne change rien). *)

let rec division liste=
    match liste with
    |[]->[],[]
    |a::[]->liste,[]
    |a::b::c->
        let (l1,l2)=division c in
        a::l1,b::l2;;
(* val division : 'a list -> 'a list * 'a list = <fun> *)

let rec fusion liste1 liste2=
    match liste1,liste2 with
    |[],_->liste2;
    |_,[]->liste1;
    |t1::q1,t2::q2->
        if t1<t2 then
            t1::(fusion q1 liste2)
        else
            t2::(fusion liste1 q2);;
(* val fusion : 'a list -> 'a list -> 'a list = <fun> *)

let rec tri_fusion liste=
    match liste with
    |[]->[];
    |a::[]->liste;
    |_ ->
        begin
            let (liste1,liste2)=division liste in
            fusion (tri_fusion(liste1)) (tri_fusion(liste2));
        end;;
(* val tri_fusion : 'a list -> 'a list = <fun> *)