Exercice: Améliorations

Exercice: Améliorations#

Notre fonction decouper, telle que vue en cours, est simple à implémenter et à une complexité linéaire. On a toutefois vu qu’il est possible de l’implémenter plus efficacement en parcourant directement la moitié des éléments pour trouver le point ou couper, soit en utilisant de pointeurs se déplaçant à des vitesses différentes. Implémentez une de ces variante et comparez les temps d’execution du tri fusion sur de grandes listes.

BEGIN SOLUTION

La version plus classique et rapide est la suivante, elle laisse la première moitié des éléments dans la liste d’origine et déplace d’un seul coup la deuxième moitié dans la liste résultat. La logique n’est pas très complexe mais les détails sur comment parcourir exactement le bon nombre d’éléments et comment calculer les longueurs des deux listes ne sont pas forcéments évidents.

On peut voir un petit gain de temps sur les listes de grandes tailles.
```
liste *decouper(liste *l) {
    liste *r = nouvelle_liste();
    if (l->nbelem < 2)
        return r;
    int n = l->nbelem / 2;
    elem *e = l->tete;  // ici e est le 1er élément de la liste l
    for (int i = 1; i < n; i++)
        e = e->next;   // à chaque i, e devient le (i+1)e élément
    r->tete = e->next; // e est le n-ième, e->next le (n+1)-ième
    e->next = NULL;
    l->nbelem = n;
    r->nbelem = l->nbelem - n;
    return r;
}
```
END SOLUTION

Notre fonction fusionner peut elle aussi est améliorée. L’utilisation de la fonction deplacer_tete permet de ne pas avoir à s’occuper du chainage mais à pour résultat de produire une liste à l’envers qu’il faut ensuite renverser.

Écrivez une nouvelle fonction fusionner qui garde un pointeur sur le dernier éléments de la liste résultat afin de pouvoir insérer les éléments directement à leur place dans la liste. Attention de bien gérer les différents cas limites.

Attention: la logique de cette fonction n’est pas très complexe mais la multiplicité des cas possibles la rend relativement longue par rapport aux autres fonction que vous avez pus écrire et rend son test difficile.

BEGIN SOLUTION

liste *fusionner(liste *l1, liste *l2) {
    liste *r = nouvelle_liste();
    // p est un pointeur vers le dernier element de la liste resultat, on
    // l'initialise à NULL pour indiquer qu'actuellement elle est vide.
    elem *p = NULL;
    while (l1->nbelem != 0 && l2->nbelem != 0) {
        // On commence par détacher le plus petit element de
        // sa liste.
        elem *e;
        if (l1->tete->val < l2->tete->val) {
            e = l1->tete;
            l1->tete = e->suivant;
            l1->nbelem--;
        } else {
            e = l2->tete;
            l2->tete = e->suivant;
            l2->nbelem;
        }
        e->suivant = NULL;
        // Puis on l'attache à la fin de la liste résultat.
        if (p == NULL)
            r->tete = e;
        else
            p->suivant = e;
        r->nbelem++;
        p = e;
    }
    // Une des deux liste est vide, il reste juste à deplacer la queue de
    // celle qui ne l'est pas vers la liste résultat.
    liste *l;
    if (l1->nbelem != 0) l = l1;
    else                 l = l2;
    if (p == NULL)
        r->tete = l->tete;
    else
        p->suivant = l->tete;
    r->nbelem += l->nbelem;
    l->nbelem = 0;
    // On n'oublie pas de libérer les listes
    liberer_liste(l1);
    liberer_liste(l2);
    return r;
}

END SOLUTION