Exercice: Tri fusion

Exercice: Tri fusion#

Nous pouvons maintenant mettre en œuvre l’algorithme de {\sl tri fusion}.

Écrivez tout d’abord une fonction permettant de découper une liste en deux listes de longueur à peu près égales. Votre fonction devra modifier la liste qui lui est donnée de manière à ce qu’elle contiennent moitié moins d’éléments et renvoyer une deuxième liste qui contiendra les éléments retirés de la première liste.
```
liste *decouper(liste *l);
```
BEGIN SOLUTION

La version la plus simple vue en cours n’est pas très efficace. Elle consiste à déplacer de manière répétée la tête de la première liste vers la deuxième jusqu’à ce que les deux listes soient équilibrées. Cette version présente de plus l’inconvénient de modifier l’ordre des éléments dans la deuxième liste, ce qui n’est pas génant pour notre cas mais réduit la généralité de la fonction. Nous tenterons d’améliorer cette fonction dans le troisième exercice.
```
liste *decouper(liste *l) {
    liste *r = nouvelle_liste();
    while (l->nbelem - r->nbelem > 1)
        deplacer_tete(l, r);
    return r;
}
```
END SOLUTION
Écrire maintenant une fonction permettant de fusionner deux listes triées en une nouvelle liste triée elle aussi :
```
liste *fusionner(liste *l1, liste *l2);
```
La manière la plus simple de fusionner deux listes triées produit une liste triée en sens inverse. N’oubliez pas les fonctions dont vous disposez pour résoudre ce problème.

Les deux listes d’origine seront détruites dans le processus, il ne faut donc pas oublier de les libérer avant de renvoyer la liste résultat.

BEGIN SOLUTION

En faisant un peu attention il est possible d’écrire cette fonction de manière à ne pas avoir de cas particulier pour les listes vides. Le seul point particulier ici est de ne pas oublier qu’une des deux listes contient encore des éléments après la boucle principale.
```
liste *fusionner(liste *l1, liste *l2) {
    liste *r = nouvelle_liste();
    while (l1->nbelem != 0 && l2->nbelem != 0) {
        if (l1->tete->val < l2->tete->val)
            deplacer_tete(l1, r);
        else
            deplacer_tete(l2, r);
    }
    while (l1->nbelem != 0)
        deplacer_tete(l1, r);
    while (l2->nbelem != 0)
        deplacer_tete(l2, r);
    r = renverser(r);
    liberer_liste(l1);
    liberer_liste(l2);
    return r;
}
```
END SOLUTION

Tout le nécéssaire est maintenant en place pour pouvoir mettre en œuvre le tri fusion. Écrivez la fonction récursive de tri qui prend en parametre une liste et qui renvoie une liste triée. La liste d’origine étant détruite dans le processus.

liste *tri_fusion(liste *l1);

BEGIN SOLUTION

liste *tri_fusion(liste *l1) {
    if (l1->nbelem < 2)
        return l1;
    liste *l2 = decouper(l1);
    l1 = tri_fusion(l1);
    l2 = tri_fusion(l2);
    l1 = fusionner(l1, l2);
    return l1;
}

END SOLUTION