Exercice: Tri par sélection

Les fonctions de manipulation de listes chaînées que nous avons développées nous permettent maintenant d’implémenter le tri par sélection sur les listes comme vu en cours.

Les principales étapes du tri par sélection d’une liste chaînée sont les suivantes :

• Créer une nouvelle liste r qui va recevoir les éléments triés.

• Tant que la liste d’origine l n’est pas vide faire :

  • Chercher le maximum m de la liste l.

  • Supprimer la valeur m de la liste l.

  • Ajouter la valeur m en tête de la liste r.

• Libérer la liste l.

• Renvoyer la liste r.

Afin de vérifier que notre implémentation est correcte, nous allons vérifier deux des invariants de cet algorithme à la fin de chaque itération :

• la somme des longueurs des deux listes est constante;

• la liste r est une liste triée.

1. Sur une feuille, dessinez la représentation en mémoire d’une liste chaînée contenant les éléments 3,4,1,5,3. Procédez de même pour une liste contenant 2,3,3,5,9.

2. On souhaite définir une fonction est_triee qui prend en paramètre une liste et renvoie un booléen indiquant si la liste est triée dans l’ordre croissant.

   bool est_triee(liste *l);
   

   Raisonnez pas à pas sur les deux exemples de liste ci-dessus pour chercher comment procéder. Puis définissez la fonction est_triee, et testez là.

   BEGIN SOLUTION

   bool est_triee(liste *l) {
       if (l->nbelem <= 1)
           return true;
       int   v = l->tete->val;
       elem *e = l->tete->next;
       while (e != NULL) {
           if (e->val < v)
               return false;
           v = e->val;
           e = e->next;
       }
       return true;
   }
   

   END SOLUTION

3. Exécutez pas à pas l’algorithme de tri par sélection sur les deux exemples de listes ci-dessus.

4. Définissez la fonction de tri par sélection en vérifiant les deux invariants à la fin de chaque itération. Si l’un des invariants n’est pas vérifié, déclenchez une exception.

   Testez votre fonction.

   liste *tri_selection(liste *l);
   

   BEGIN SOLUTION

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

   END SOLUTION