Vérifier expérimentalement que tri selection compte renvoie exactement…

Application directe du cours · niveau 2 · NSI (première), chapitre 7 — Parcourir, trier, prouver · Dérouler, compter, vérifier

Énoncé

Vérifier expérimentalement que tri_selection_compte renvoie exactement $n (n - 1) /2$ pour toutes les tailles de 1 à 100, quel que soit le contenu.

Corrigé

« Quel que soit le contenu » est la partie intéressante : il faut donc varier le contenu, pas seulement la taille.


import random
random.seed(84)
for n in range(1, 101):
    attendu = n * (n - 1) // 2
    for etat in ("trie", "envers", "alea", "egaux"):
        if etat == "trie":     t = list(range(n))
        elif etat == "envers": t = list(range(n, 0, -1))
        elif etat == "alea":   t = [random.randint(0, 100) for _ in range(n)]
        else:                  t = [7] * n
        assert tri_selection_compte(t) == attendu, (n, etat)

$100 \times 4 = 400$ cas passent, aucune assertion ne se déclenche.

$n$	$n (n - 1) /2$
$1$	$0$
$2$	$1$
$10$	$45$
$100$	$4950$

Pourquoi le contenu n'y change rien. Les deux boucles sont des for sur des range qui ne dépendent que de $n$ . Le contenu décide seulement de la valeur de m, jamais du nombre de tours. Le tri par sélection n'a donc ni meilleur ni pire cas — c'est ce que le cours annonçait, et l'expérience le confirme sur quatre familles de tableaux, dont les deux extrêmes.

Le cas $n = 1$ mérite d'être dans le lot : $1 \times 0/2 = 0$ , aucune comparaison. Un tableau d'un élément est déjà trié, et l'algorithme le sait sans rien faire.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.