---
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: Tri par sélection optimisé

L'implémentation précédente du tri par sélection n'est pas optimale. En effet,
elle parcourt deux fois la liste $l$ à chaque itération, une fois pour chercher
le maximum et une fois pour le supprimer de la liste. Il est possible d'ajouter
une fonction de manipulation de listes effectuant ces deux opérations
simultanément en mémorisant l'élément précédent celui contenant le maximum. Avec
cette nouvelle fonction il est ensuite possible d'implémenter le tri par
sélection de manière plus optimisée.

:::{attention}
Comme vu en cours, cette modification rend l'algorithme plus rapide
mais ne change pas sa complexité qui reste quadratique. Cette version
n'est plus rapide que d'un facteur constant.
:::


1.  Commencez par définir une fonction utilisant l'optimisation
    décrite ci-dessus pour rechercher et supprimer la valeur maximale
    d'une liste, avant de la renvoyer :

    ```cpp
    int supprimer_maximum(liste *l);
    ```

	:::{attention}
	Cette fonction est relativement technique. Testez-la bien en
    profondeur, aussi bien sur des cas simples que complexes, avant de
    passer à la suivante.
	:::

    BEGIN SOLUTION

    ```cpp
    int supprimer_maximum(liste *l) {
        if (l->nbelem == 0)
            return -1;
        int max = l->tete->val;
        elem *e = l->tete->next;
        elem *p = l->tete; // Element précédent e
        elem *q = NULL;    // Element precedent le maximum
        // Recherche du maximum en gardant trace de l'élément qui le
        // précède dans la liste.
        while (e != NULL) {
            if (e->val > max) {
                max = e->val;
                q = p;
            }
            p = e;
            e = e->next;
        }
        // Suppression du maximum : Si le maximum est en tête de 
        // liste, il faut mettre à jour la tête.
        if (q == NULL) {
            e = l->tete;
            l->tete = e->next;
        // Sinon il faut mettre à jour le lien suivant de l'élément
        // précédent.
        } else {
            e = q->next;
            q->next = e->next;
        }
        free(e);
        l->nbelem- -;
        return max;
    }
    ```

    END SOLUTION

2.  Redéfinissez maintenant votre fonction de tri par sélection de
    manière plus optimisée en utilisant cette nouvelle fonction de
    manipulation de liste.

    BEGIN SOLUTION

    ```cpp
    liste *tri_selection_optimisee(liste *l) {
        int k = l->nbelem;
        liste *r = nouvelle_liste();
        while (l->nbelem != 0) {
            int max = supprimer_maximum(l);
            ajouter_en_tete(r, max);
            // vérification des invariants
            if (l->nbelem + r->nbelem != k) {
                cout << "|l| + |r| invalide" << endl;
            }
            if (esttriee(r) == false) {
                cout << "r n'est pas triée" << endl;
            }
        }
        liberer_liste(l);
        return r;
    }
    ```

    END SOLUTION

3.  Il existe un autre invariant que nous avons vu en cours pour le
    tri par sélection. Les éléments de la première liste doivent être
    inférieurs ou égaux aux éléments de la seconde. Ajoutez la
    vérification de cet invariant à votre boucle.