Exercice: Tri par sélection rapide

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 efficace.

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 :

   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

   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 efficace en utilisant cette nouvelle fonction de manipulation de liste.

   BEGIN SOLUTION

   liste *tri_selection_rapide(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.