Le principe est le suivant :
- on commence par partager le tableau (ou la liste) en deux parties de longueur à peu près égales
- on trie récursivement les deux parties
- on fusionne ces deux parties pour obtenir le tableau (la liste) triée
Remarque : la division en deux parties est simple car on coupe selon la première idée venue (séparation spatiale), mais la fusion est plus délicate (notamment sur les tableaux !).
8.1.1 Tri fusion d'une liste
La fonction split sépare une liste en deux parties de tailles égales (à une unité près)
|
1 2 3 4 |
let rec split l = match l with | [] -> [],[] | t::q -> let (q0,q1) = split q in t::q1, q0;; val split : 'a list -> 'a list * 'a list = <fun> |
|
1 2 |
split [0;1;2;3;4;5;6];; - : int list * int list = ([0;2;4;6], [1;3;5]) |
La fonction merge fusionne deux listes supposées triées dans l’ordre croissant :
|
1 2 3 4 5 6 |
let rec merge l1 l2 = match l1,l2 with | [], _ -> l2 | _, [] -> l1 | t1::q1, t2::q2 -> if t1<t2 then t1::(merge q1 l2) else t2::(merge l1 q2);; val merge : 'a list -> 'a list -> 'a list = <fun> |
|
1 2 |
merge [0;4;7;10] [1;3;8];; - : int list = [0; 1; 3; 4; 7; 8; 10] |
La fonction tri_fusion trie récursivement une liste :
|
1 2 3 4 5 |
let rec tri_fusion l = match l with | [] -> [] | [x] -> [x] | _ -> let (l0,l1) = split l in merge (tri_fusion l0) (tri_fusion l1);; val tri_fusion : 'a list -> 'b list = <fun> |
|
1 2 |
tri_fusion [7; 1; 5; 4; 9; 2; 11; 3];; - : int list = [1; 2; 3; 4; 5; 7; 9; 11] |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres