Vous avez maintenant vu le tri par sélection, dont le fonctionnement est assez naturel. Vous vous dites peut-être que finalement, ce tuto est assez inutile, puisqu'il ne fait que parler longuement de chose assez évidentes. Découvrir que pour trier une liste il faut commencer par chercher le plus petit élément, merci, votre petite soeur de deux ans et demi l'aurait deviné (et en plus, elle est mignonne, et elle mange de la purée de potiron, avantages décisifs qui manquent à ce modeste tutoriel).
Nous allons maintenant voir un autre tri, le tri par fusion. Il est surprenant par deux aspects, qui sont très liés :
- il n'est pas du tout naturel au départ ;
- il est beaucoup plus efficace que les tri quadratiques vus jusqu'à présent.
C'est en effet un tri qui a une complexité bien meilleure que les tris par sélection ou insertion. On ne le voit pas sur un petit nombre d'élément, mais sur de très gros volumes c'est décisif. Nous verrons sa complexité en détail après avoir décrit l'algorithme.
Algorithme
L'idée du tri par fusion se décrit en une phrase :
Citationon coupe la liste en deux parts égales, on trie chaque moitié, et on fusionne les deux demi-listes
Vous avez bien entendu reconnu une approche de type "diviser pour régner" : on découpe le problème (un tableau => deux demi-tableaux), on traite chaque sous-problème séparément, puis on rassemble les résultats de manière intelligente.
Évidemment, tout le sel de la chose se situe dans la phase de
fusion : on a deux demi-listes triées, et on veut obtenir une liste triée. On pourrait se dire qu'il suffit de mettre les deux listes bout à bout, par exemple si on a les deux listes triées
[1; 2; 3] et
[4;
5; 6], on les colle et pouf
[1;2;3;4;5;6]. Malheureusement, ça ne marche pas, prenez par exemple
[1; 3; 6] et
[2; 4; 5]. Il y a bien quelque chose à faire, et ce
quelque chose a intérêt à être efficace : si cette opération cruciale du tri est trop lente, on peut jeter l'ensemble.
L'idée qui permet d'avoir une fusion efficace repose sur le fait que les deux listes sont triées. Il suffit en fait de les parcourir dans l'ordre : on sait que les plus petits éléments des deux listes sont au début, et le plus petit élément de la liste globale est forcément soit le plus petit élément de la première liste, soit le plus petit élément de la deuxième (c'est le plus petit des deux). Une fois qu'on l'a déterminé, on le retire de la demi-liste dans laquelle il se trouve, et on recommence à regarder les éléments du début. Une fois qu'on a épuisé les deux demi-listes, on a bien effectué la fusion.
Implémentation avec des listes
Commençons par coder l'opération de fusion d'un couple de listes :
- si l'une des listes est vide, on renvoie l'autre liste ;
- sinon, on compare les têtes de chaque liste, on prend la plus petite et on rappelle la fusion sur la queue de cette liste, et l'autre demi-liste.
En Caml :
Code : OCaml | let rec fusion = function
| ([], li) | (li, []) -> li
| tete_a::queue_a, tete_b::queue_b ->
let bonne_tete, queue, autre_demi_liste =
if tete_a < tete_b
then tete_a, queue_a, tete_b::queue_b
else tete_b, queue_b, tete_a::queue_a in
bonne_tete :: fusion (queue, autre_demi_liste)
|
En C :
Secret (cliquez pour afficher)La version la plus simple est la suivante :
Code : C | List *fusion(List *gauche, List *droite)
{
if (NULL == gauche)
return droite;
if (NULL == droite)
return gauche;
if (gauche->val <= droite->val)
return cons(gauche->val, fusion(gauche->next, droite));
else
return cons(droite->val, fusion(gauche, droite->next));
}
|
Cette version pose cependant un problème. Comme j'en ai déjà parlé pour
l'opération de concaténation, il faut parfois faire attention aux risques d'effets de bord : si on modifie la liste de résultat, est-ce que les listes de départ sont modifiées ?
Dans l'implémentation que je viens de donner, la réponse est
oui : quand on fusionne deux listes, si on arrive à la fin de la liste de gauche (
NULL == gauche), alors on renvoie la liste de droite (
return droite;). Cela veut dire que si on modifie la fin de la liste, la liste de droite qu'on a passé en paramètre sera modifiée aussi :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | void print_list(List *liste)
{
while (NULL != liste) {
printf("%d ", liste->val);
liste = liste->next;
}
printf("\n");
}
int main()
{
List *a, *b, *c;
printf("Éléments de a :\n");
a = cons(1, NULL);
print_list(a);
printf("Éléments de b :\n");
b = cons(2, cons(3, NULL));
print_list(b);
printf("Éléments de c = fusion(a,b) :\n");
c = fusion(a, b);
print_list(c);
printf("Modification du troisième élément c :\n");
c->next->next->val = 5;
print_list(c);
printf("Est-ce que b a été modifiée ?\n");
print_list(b);
free_list(a);
free_list(c);
return 0;
}
|
La dernière ligne affiche "2 5" : b a été modifiée quand on a changé c !
Ce comportement est dangereux et risque de conduire à des bugs (question bonus : pourquoi seulement
free_list(a); free_list(c); ?). On peut peut-être s'en sortir (en faisant attention à ne faire des fusions que de listes temporaires dont on n'aura pas besoin ensuite), mais je préfère m'assurer qu'il n'y a aucun risque et coder une nouvelle version de
fusion qui
copie les éléments des listes au lieu de les reprendre directement. Ce sera un peu moins rapide, mais la complexité sera la même, et les chances de bugs plus petites. Si vous aimez jouer avec le feu, vous pouvez essayer de coder
tri_fusion sans ces copies supplémentaires.
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | List *copy_list(List *liste)
{
if (NULL == liste)
return NULL;
else return cons(liste->val, copy_list(liste->next));
}
List *fusion(List *gauche, List *droite)
{
if (NULL == gauche)
return copy_list(droite);
else if (NULL == droite)
return copy_list(gauche);
else if (gauche->val <= droite->val)
return cons(gauche->val, fusion(gauche->next, droite));
else
return cons(droite->val, fusion(gauche, droite->next));
}
|
Il y a une autre opération à implémenter : la découpe d'une liste en deux demi-listes. On parcourt la liste par bloc de deux éléments, en ajoutant le premier dans la demi-liste de gauche, le deuxième dans la demi-liste de droite. S'il reste moins de deux éléments, on met la liste n'importe où (par exemple à gauche) et on met une liste vide de l'autre côté.
En Caml :
Code : OCaml | let rec decoupe = function
| ([] | [_]) as liste -> (liste, [])
| gauche::droite::reste ->
let (reste_gauche, reste_droite) = decoupe reste in
gauche :: reste_gauche, droite :: reste_droite
|
En C :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13 | void decoupe(List *liste, List **gauche, List **droite)
{
do {
if (NULL != liste) {
*gauche = cons(liste->val, *gauche);
liste = liste->next;
}
if (NULL != liste) {
*droite = cons(liste->val, *droite);
liste = liste->next;
}
} while (NULL != liste);
}
|
On peut alors écrire facilement le tri (s'il reste moins de deux éléments, la liste est déjà triée donc on la renvoie directement) :
En Caml :
Code : OCaml | let rec tri_fusion = function
| ([] | [_]) as liste_triee -> liste_triee
| liste ->
let demi_gauche, demi_droite = decoupe liste in
fusion (tri_fusion demi_gauche, tri_fusion demi_droite)
|
En C :
Secret (cliquez pour afficher)Dans l'implémentation en C, il faut faire attention à bien libérer la mémoire allouée par les listes temporaires : les résultats de
decoupe,
fusion et
tri_fusion.
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | List *tri_fusion(List *liste)
{
if (NULL == liste || NULL == liste->next)
return copy_list(liste);
else {
List *gauche, *droite, *gauche_triee, *droite_triee, *resultat;
/* au début, gauche et droite sont vides */
gauche = NULL;
droite = NULL;
/* on decoupe la liste en gauche et droite */
decoupe(liste, &gauche, &droite);
/* on trie gauche et droite, avant de les libérer */
gauche_triee = tri_fusion(gauche);
droite_triee = tri_fusion(droite);
free_list(gauche);
free_list(droite);
/* on fait la fusion des deux listes triées, avant de les libérer */
resultat = fusion(gauche_triee, droite_triee);
free_list(gauche_triee);
free_list(droite_triee);
/* il ne reste plus qu'à renvoyer le résultat */
return resultat;
}
}
|
Code de test :
Code : C | int main()
{
List *a, *b, *c;
a = cons(1, cons(5, cons(4, cons(3, cons(6, NULL)))));
b = tri_fusion(a);
print_list(a);
print_list(b);
free_list(a);
free_list(b);
return 0;
}
|
Implémentation avec des tableaux
L'implémentation avec des tableaux a des avantages et des inconvénients.
- La phase de découpe est très simple : comme on connaît à l'avance la taille du tableau, il suffit de la diviser par deux et de couper au milieu
- l'opération de fusion est moins naturelle : il faut manipuler les indices
On commence par coder l'opération de fusion. On procède à peu près comme pour les listes, sauf qu'au lieu d'utiliser une procédure récursive, on utilise une boucle pour parcourir les tableaux. On doit conserver trois indices différents :
- la position de lecture dans le premier demi-tableau
- la position de lecture le deuxième demi-tableau
- la position d'écriture dans le tableau résultat
Le dernier indice évolue de façon prévisible : à chaque fois qu'on choisit un élément dans l'une des demi-listes, il augmente de 1. On peut donc l'utiliser comme indice d'une boucle
for.
Quand on compare les éléments en tête des deux demi-listes, il faut faire attention à vérifier qu'aucune demi-liste n'est "épuisée" (on a pris tous ses éléments, donc l'indice correspondant est supérieur ou égal à sa taille).
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | <?php
function fusion($tab_g, $tab_d)
{
$taille_g = count($tab_g);
$taille_d = count($tab_d);
$res = array(); // tableau résultat
$i_g = 0; $i_d = 0; // indices de lecture, g->gauche, d->droite
for ($i = 0; $i_g < $taille_g && $i_d < $taille_d; ++$i)
if ($tab_g[$i_g] <= $tab_d[$i_d])
$res[$i] = $tab_g[$i_g++];
else
$res[$i] = $tab_d[$i_d++];
/* on copie le reste du tableau de gauche (s'il reste quelque chose) */
while ($i_g < $taille_g)
$res[$i++] = $tab_g[$i_g++];
/* pareil pour le tableau de droite */
while ($i_d < $taille_d)
$res[$i++] = $tab_d[$i_d++];
return $res;
}
?>
|
On utilise une fonction
copie pour récupérer chaque demi-tableau dans un tableau à part, avant de les trier.
Code : PHP | <?php
function copie($tab, $debut, $fin)
{
$res = array();
for ($i = $debut; $i <= $fin; ++$i)
$res[$i - $debut] = $tab[$i];
return $res;
}
?>
|
On peut alors écrire le tri entier.
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | <?php
function tri_fusion($tab)
{
$taille = count($tab);
if ($taille <= 1)
return $tab;
else {
$milieu = (int)($taille / 2);
$gauche = copie($tab, 0, $milieu-1);
$droite = copie($tab, $milieu, $taille-1);
return fusion(tri_fusion($gauche), tri_fusion($droite));
}
}
// exemple :
$tab = array(1,5,4,3,6);
print_r(tri_fusion($tab));
?>
|
On a utilisé une fonction
copie pour copier les deux demi-tableaux en dehors du tableau avant de les trier et de les fusionner. La procédure fusion, elle aussi, crée un nouveau tableau, qu'elle renvoie. On a donc alloué de nouveaux tableaux, ce n'est pas un tri en place. Il est possible de faire mieux : on peut, en manipulant des indices au lieu de tableaux complets, trier les demi-tableau dans le tableau initial, ce qui le modifie mais permet de ne pas allouer de mémoire supplémentaire. Par contre, pour l'étape de fusion il faut tout de même copier des informations, par exemple les deux demi-tableaux triés. Ce n'est toujours pas un tri en place. Il est en fait possible de recopier seulement le demi-tableau de gauche.
Exercice : Écrire (dans le langage de votre choix) un tri fusion sur les tableaux ne recopiant que le demi-tableau de gauche. Pourquoi ça marche ?
Remarque : Il existe des version complètement en place du tri fusion (sans aucune recopie), mais elles sont nettement plus compliquées et souvent moins rapides. Il faut faire un compromis, et la simplicité est souvent le meilleur objectif.
Complexité
L'étude de la complexité du tri par fusion est assez simple. On commence avec une liste (ou un tableau) de N éléments. On le découpe, ce qui fait deux tableaux de N/2 éléments. On les découpe, ce qui fait 4 tableaux de N/4 éléments. On les découpe, ce qui fait 8 tableaux ...
Quand est-ce que la phase de découpage s'arrête ? Quand on est arrivé à des tableaux de taille 1. Et combien de fois faut-il diviser N par 2 pour obtenir 1 ? On l'a déjà vu, c'est la fonction logarithme ! En effet, si on a un tableau de taille 1, on renvoie le tableau en une seule opération (f(0) = 1), et si on double la taille du tableau il faut faire une découpe de plus (f(2*N) = f(N) + 1). C'est bien notre sympathique fonction du chapitre précédent. On a donc log(N) phases de "découpe" successives.
Quel est le travail effectué à chaque étape ? C'est le travail de fusion : après le tri, il faut fusionner les demi-listes. Notre algorithme de fusion est linéaire : on parcours les deux demi-listes une seule fois, donc la fusion de deux tableaux de taille N/2 est en O(N).
Vous allez sûrement me faire remarquer que plus on découpe, plus on a de fusions à faire : au bout de 4 étapes de découpe, on se retrouve avec 16 tableaux à fusionner ! Oui, mais ces tableaux sont petits, ils ont chacun N/16 élément. Au total, on a donc 16 * N/16 = N opérations lors des fusions de ces tableaux : à chaque étape, on a O(N) opérations de fusion.
On a donc log(N) étapes à O(N) opérations chacune. Au total, cela nous fait donc O(N * log(N)) opérations : la complexité du tri fusion est en O(N * log(N)) (parfois noté simplement O(N log N), la multiplication est sous-entendue).
Efficacité en pratique
On est passé, en changeant d'algorithme, d'une complexité de O(N
2) à une complexité de O(N * log(N)). C'est bien gentil, mais est-ce si génial que ça ?
La réponse est
oui : O(N log(N)) ça va
vraiment beaucoup plus vite. Pour vous en convaincre, voici des timings concrets comparant une implémentation du tri par sélection (avec des tableaux) et du tri par fusion (avec des listes), le tout dans le même langage de programmation et sur le même (vieil) ordinateur pour pouvoir comparer :
| N | sélection | fusion |
|---|
| 100 |
0.006s |
0.006s |
| 1000 |
0.069s |
0.010s |
| 10 000 |
2.162s |
0.165s |
| 20 000 |
7.526s |
0.326s |
| 40 000 |
28.682s |
0.541s |
Les mesures confirment ce que nous avons expliqué jusqu'à présent. On parle bien d'une complexité
asymptotique, pour des N grands. Quand N est petit, les deux algorithmes sont à peu près équivalents (pour un petit nombre d'éléments, le tri par insertion va même un peu plus vite que le tri par fusion). La différence se fait sur de grandes valeurs, mais surtout elle caractérise l'
évolution des performances quand les demandes changent. Avec une complexité de O(N
2 ), si on double la taille de l'entrée, le tri par sélection va environ 4 fois plus lentement (c'est assez bien vérifié sur nos exemples). Avec une complexité de O(N * log(N)), cela va seulement un peu plus de 2 fois plus lentement environ (vu les petits temps de calcul, les mesures sont plus sensibles aux variations, donc moins fiables).
En extrapolant ce comportement, on obtient sur de très grandes données un fossé absolument gigantesque. Par exemple, dans ce cas précis, le tri fusion sur 10 millions d'éléments devrait prendre environ une demi heure, alors que pour un tri par sélection il vous faudra... un an et demi.
Ce genre de différences n'est pas un cas rare. On est passé d'un facteur N à un facteur log(N), ce qui est plutôt courant quand on passe d'un code "naïf" (sans réflexion algorithmique) à quelque chose d'un peu mieux pensé. Cela vous donne une idée des gains que peut vous apporter une connaissance de l'algorithmique.
Introduction au problème du tri
bluestorm
.
Trouvez une formation
Suggestions
Twitter
Facebook
Google+