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 liste 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 est plus rapide d’un facteur constant.

1. Commencez donc par implémenter une fonction qui recherche et supprime la valeur maximale d’une liste et la renvoie :

   int supprimer_maximum(liste *l);
   

   Attention: cette fonction est relativement complexe à écrire. 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. Réécrivez 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 plus petits que les éléments de la seconde. Ajouter la vérification de cet invariant à votre boucle.