Aller au contenu

TP Python – Tris, comparaisons et choix

BTS SIO SISR 2e année – Pour aller plus loin – S14

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Tri par sélection

Écris tri_selection(L) qui renvoie une nouvelle liste triée (sans modifier L), par la méthode de sélection. Pas de sorted.

J'anticipe. Rappelle la trace de l'exercice 1.

###
assert tripy-undselection([5, 2, 9, 1, 7]) == [1, 2, 5, 7, 9]bksl-nlassert tripy-undselection([]) == []bksl-nlassert tripy-undselection([3]) == [3]bksl-nlassert tripy-undselection([2, 2, 1]) == [1, 2, 2]bksl-nlassert tripy-undselection([3, 2, 1]) == [1, 2, 3]bksl-nlassert all(tripy-undselection(L) == sorted(L) for L in [[4, 1, 3, 2], [1, 1, 1], [9, -2, 0, 5, 5]])bksl-nlbksl-nl ∞/∞

def tripy-undselection(L):bksl-nl """Nouvelle liste triee, par selection."""bksl-nl ...bksl-nlbksl-nl

Exercice B – Tri par insertion

Écris tri_insertion(L) qui renvoie une nouvelle liste triée, par insertion, sans sorted.

###
assert tripy-undinsertion([5, 2, 9, 1, 7]) == [1, 2, 5, 7, 9]bksl-nlassert tripy-undinsertion([]) == []bksl-nlassert tripy-undinsertion([3]) == [3]bksl-nlassert tripy-undinsertion([2, 2, 1]) == [1, 2, 2]bksl-nlassert tripy-undinsertion([3, 2, 1]) == [1, 2, 3]bksl-nlassert all(tripy-undinsertion(L) == sorted(L) for L in [[4, 1, 3, 2], [1, 1, 1], [9, -2, 0, 5, 5]])bksl-nlbksl-nl ∞/∞

def tripy-undinsertion(L):bksl-nl """Nouvelle liste triee, par insertion."""bksl-nl ...bksl-nlbksl-nl

Exercice C – Comparaisons de la sélection

Écris comparaisons_selection(L) qui renvoie le nombre de comparaisons L[j] < L[m] faites par le tri par sélection de L. Pense à la formule : tu peux la programmer directement ou compter dans la boucle.

###
assert comparaisonspy-undselection([5, 2, 9, 1, 7]) == 10bksl-nlassert comparaisonspy-undselection([]) == 0bksl-nlassert comparaisonspy-undselection([4]) == 0bksl-nlassert comparaisonspy-undselection([1, 2, 3, 4, 5, 6, 7, 8]) == 28bksl-nlassert comparaisonspy-undselection([8, 7, 6, 5, 4, 3, 2, 1]) == 28bksl-nlbksl-nl ∞/∞

def comparaisonspy-undselection(L):bksl-nl """Nombre de comparaisons du tri par selection."""bksl-nl ...bksl-nlbksl-nl

Exercice D – Comparaisons de l'insertion

Écris comparaisons_insertion(L) qui compte les évaluations de L[j - 1] > x dans le tri par insertion de L (la condition j > 0 n'est pas comptée).

J'anticipe. Retrouve 7 pour [5, 2, 9, 1, 7] (exercice 2).

###
assert comparaisonspy-undinsertion([5, 2, 9, 1, 7]) == 7bksl-nlassert comparaisonspy-undinsertion([1, 2, 3, 4, 5]) == 4bksl-nlassert comparaisonspy-undinsertion([5, 4, 3, 2, 1]) == 10bksl-nlassert comparaisonspy-undinsertion([]) == 0bksl-nlassert comparaisonspy-undinsertion([9]) == 0bksl-nlbksl-nl ∞/∞

def comparaisonspy-undinsertion(L):bksl-nl """Nombre de comparaisons L[j-1] > x du tri par insertion."""bksl-nl ...bksl-nlbksl-nl

Exercice E – Coût de k recherches

Écris cout_recherches(n, k) qui renvoie le couple (sequentielle, tri_dicho) avec sequentielle = k * n et tri_dicho = round(n * log2(n)) + k * (floor(log2(n)) + 1) pour n >= 2.

J'anticipe. Retrouve le tableau du cours pour n = 1000.

###
assert coutpy-undrecherches(1000, 1) == (1000, 9976)bksl-nlassert coutpy-undrecherches(1000, 10) == (10000, 10066)bksl-nlassert coutpy-undrecherches(1000, 11) == (11000, 10076)bksl-nlassert coutpy-undrecherches(100000, 1000) == (100000000, 1677964)bksl-nlbksl-nl ∞/∞

def coutpy-undrecherches(n, k):bksl-nl """Renvoie (cout sequentiel, cout tri + dichotomie)."""bksl-nl ...bksl-nlbksl-nl

Je comprends. Que représente le terme round(n * log2(n)) ?

Exercice F – Quelle stratégie ?

Écris meilleur_choix(n, k) qui renvoie "sequentielle" si son coût est inférieur ou égal à celui de tri + dichotomie, sinon "tri+dicho". Utilise la même formule qu'en E (recopie-la).

###
assert meilleurpy-undchoix(1000, 1) == "sequentielle"bksl-nlassert meilleurpy-undchoix(1000, 10) == "sequentielle"bksl-nlassert meilleurpy-undchoix(1000, 11) == "tri+dicho"bksl-nlassert meilleurpy-undchoix(100000, 1000) == "tri+dicho"bksl-nlbksl-nl ∞/∞

def meilleurpy-undchoix(n, k):bksl-nl """"sequentielle" ou "tri+dicho" selon le cout."""bksl-nl ...bksl-nlbksl-nl