Exercice: Tri par sélection

Exercice: Tri par sélection#

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

liste *tri_selection(liste *l);

Les principales étapes du tri 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

  • Retourner 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. Écrire une fonction est_triee qui prend en paramètre une liste et renvoie un booléen indiquant si la liste est bien triée dans l’ordre croissant.

    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

  2. Écrire maintenant la fonction de tri par sélection sur les listes en vérifiant bien que les invariants sont vérifiés à la fin de chaque itération.

    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 (esttriee(r) == false) {
            cout << "r n'est pas triée" << endl;
        }
    }
    liberer_liste(l);
    return r;
}

    END SOLUTION