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

Parcourir, trier, prouver · Dérouler, compter, vérifier · niveau 2

É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.