---
# System prepended metadata

title: 121a - TD 8 - 02-04-21 PM

---

# 121a - TD 8 - 02-04-21 PM
```cpp=

struct elem {
	elem *next;
	int val;
	};
struct liste {
	elem *tete;
	int nbelem;
	};

// exercice 1

bool est_triee(liste *l){
    if (l->nbElem == 0){
        return true;
    } 
    elem *e = l->tete;
    while (e->next != NULL){
        elem *eNext = e->next;
        if (eNext->val < e->val){
            return false;
        }
        e = eNext;
    }
    return true;
}


liste *tri_selection(liste *l) {
	liste *r = nouvelle_liste();
	int maxi;
    int s = l->nbelem;
	while (l->tete != NULL) {
		maxi = chercher_maximum(l);
		ajouter_en_tete(r,maxi);
		supprimer_valeur(l,maxi);
        if(l->nbelem + r->nbelem != s) {
        cout << "nbelem pas constant"; 
        break;
        }
        if(not est_triee(r)) {        // if (est_triee(r) == false)
            cout << "liste mal triée"; 
            break;
        }
        
	}
	return r;
}





liste *tri_selection(liste *l) {
        liste *r = nouvelle_liste();
        int nbelems=l->nbelem;
        int maxi;
        while (l->tete != NULL) {
                maxi = chercher_maximum(l);
                ajouter_en_tete(r,maxi);
                supprimer_valeur(l,maxi);
                if(nbelems!=(l->nbelem + r->nbelem) or not(est_triee(r))){
                        throw runtime_error("cé pa bon");
                }
        }
        return r;
}




// exercice 2




int supprimer_maximum(liste *l){
    if (l->nbElem == 0){
        throw runtime_error("la liste ne contient pas d'éléments");
    }
    elem *e = l->tete;
    elem *precede;
    precede = NULL;
    int max = e->val;
    while (e->next != NULL){
        elem *eNext = e->next;
        if (eNext->val > max){
            max = eNext->val;
            precede = e;
        }
        e = eNext;
    }
    elem *suppr;
    if (precede == NULL){
        suppr = l->tete;
        l->tete = suppr->next;
        max = suppr->val;
        free(suppr);
        l->nbElem--;
        return max;
    }
    suppr = precede->next;
    precede->next = suppr->next;
    max = suppr->val;
    free(suppr);
    l->nbElem--;
    return max;
}


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);
		if (l->nbelem + r->nbelem != k) {
			cout << "|l| + |r| invalide\n";
		}
		if (est_triee(r) == false) {
			cout << "r n’est pas triée\n";
		}
	}
	liberer_liste(l);
	return r;
}






























```