corrigé des deux tris

MPSI {831, 832}
Lycée Masséna
TP 4 : Corrigé Tri Fusion et Tri Rapide
Tout d’abord, une fonction pour générer des tableaux aléatoires :
let random_list n m=
let rec aux acc n=match n with
| 0 -> acc
| _ -> aux (random__int m::acc) (n-1)
in aux [] n
;;
1
Le Tri Fusion
1. Tout d’abord, on écrit une fonction fission l prenant en entrée une liste et retournant deux listes de même
taille (à un élément près) dont les éléments réunis sont les mêmes que ceux de `.
let fission l=
let rec aux acc1 acc2 l n=
match (l,n) with
| [],_ -> acc1,acc2
| a::q,0 -> aux (a::acc1) acc2 q 1
| a::q,_ -> aux acc1 (a::acc2) q 0
in aux [] [] l 0
;;
La fonction auxiliaire interne prend en paramètres deux accumulateurs (nos futures listes renvoyées), une liste
(celle à vider), et un entier n qui prend toujours les valeurs 0 et 1. L’idée est de remplir soit le premier accumulateur soit le second, ceci étant décidé suivant la valeur de n. Lorsqu’on rappelle la fonction auxiliaire, on
modifie n pour changer la liste dans laquelle on va ajouter le prochain élément. Une autre idée : prendre les
éléments deux par deux (dernier cas de filtrage de la forme x::y::q). Si la liste n’a qu’un élément, on le met
dans un des deux accumulateurs de façon arbitraire.
2. Pour fusionner, on introduit également une fonction auxiliaire avec accumulateur. On distingue les cas :
— les deux listes sont vides (on a terminé !) ;
— l’une des deux est vide (on remplit l’accumulateur avec l’autre) ;
— les deux sont non vides : on choisit le plus petit des deux éléments de tête pour le mettre dans l’accumulateur.
On remplit ainsi l’accumulateur, qui en sortie de fonction auxiliaire est trié dans l’ordre décroissant. On l’inverse
donc (avec rev).
let fusion l1 l2=
let rec aux acc l1 l2=match l1,l2 with
| [],[] -> acc
| x::q,[] -> aux (x::acc) q []
| [],x::q -> aux (x::acc) q []
| x1::q1,x2::_ when x1<=x2 -> aux (x1::acc) q1 l2
| _,x::q -> aux (x::acc) l1 q
in rev (aux [] l1 l2)
;;
Svartz
Page 1/2
2014/2015
MPSI {831, 832}
Lycée Massena
Une fois une des deux listes vides dans la fonction auxiliaire, on pourrait aussi stopper les appels récursifs en
utilisant rev (pour inverser) et @ (pour concaténer).
3. Le tri est maintenant facile à écrire :
— si la liste a 1 élément (ou zéro) elle est triée ;
— sinon, on coupe notre liste en deux, on trie récursivement les deux listes, et on les fusionne.
let rec tri_fusion l=match l with
| [] | [_] -> l
| _ -> let l1,l2=fission l in fusion (tri_fusion l1) (tri_fusion l2)
;;
4. La complexité est en O(n log(n)), avec n la taille de la liste à trier. Voir le cours !
2
Tri Rapide
1. Si la liste est vide, on renvoie une erreur, sinon on procède avec une fonction récursive auxiliaire : on utilise deux
accumulateurs (qui sont des listes). On parcourt récursivement la liste passée en entrée en ajoutant l’élément
courant au premier ou au deuxième accumulateur suivant s’il est supérieur ou inférieur au pivot x.
let partition l=match l with
| [] -> failwith "liste vide"
| x::q -> let rec aux acc1 acc2 l=begin
match l with
| [] -> x,acc1,acc2
| y::t when y<= x -> aux (y::acc1) acc2 t
| y::t -> aux acc1 (y::acc2) t
end
in aux [] [] q
;;
2. Là encore, le tri est facile à écrire : si la liste est vide ou possède un seul élément, elle est triée. Sinon, on utilise
la fonction de partition, et on appelle récursivement le tri sur les deux parties. Il est facile de recomposer une
liste triée à partie du pivot et des deux sous-listes triées : on intercale le pivot entre les deux sous-listes.
let rec tri_rapide l=match l with
| [] | [_] -> l
| _ -> let x,acc1,acc2=partition l in (tri_rapide acc1) @ (x::(tri_rapide acc2))
;;
Svartz
Page 2/2
2014/2015

Download Report