---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17
---

+++ {"tags": ["solution"]}

# Exercice: Optimisations

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

   BEGIN SOLUTION

   La version la 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.

   ```cpp
   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++)
   		// Invariant: e est le i-ème élément
           e = e->next;
   	// ici e est le n-ième, e->next le (n+1)-ième
       r->tete = e->next;
       e->next = NULL;
       r->nbelem = l->nbelem - n;
       l->nbelem = n;
       return r;
   }
   ```

   END SOLUTION

2. Notre fonction fusionner peut elle aussi être optimisée: l'utilisation de la fonction
   `deplacer_tete` permet en effet de ne pas avoir à s'occuper du chaînage mais a pour
   résultat de produire une liste à l'envers qu'il faut ensuite renverser.

   Définissez une nouvelle fonction `fusionner` qui garde un pointeur sur le dernier
   élément de la liste résultat afin de pouvoir insérer les éléments directement à leur
   place dans la liste.

   :::{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 fonctions que vous avez
   pu écrire et rend son test plus difficile.

   Veillez notamment à bien gérer les différents cas limites.
   :::

   BEGIN SOLUTION

   ```cpp
   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