Chronométrer les deux tris du cours plutôt que compter leurs…

import time

def duree(f, t, repet=3):
    """Meilleur temps sur plusieurs exécutions, en secondes."""
    meilleur = None
    for _ in range(repet):
        c = list(t)
        debut = time.perf_counter()
        f(c)
        ecoule = time.perf_counter() - debut
        meilleur = ecoule if meilleur is None else min(meilleur, ecoule)
    return meilleur

Pour référence, les rapports du comptage des comparaisons sur les mêmes tailles valent $4,01$, $4,005$, $4,003$ — trois décimales exactes.

Oui, la loi est là. Les rapports de temps tournent autour de $4$ : le coût est bien quadratique, et la mesure le montre. Mais ils oscillent entre $3,94$ et $5,16$, alors que le comptage donne $4,00$ à trois décimales près.

Pourquoi le temps est moins fiable. Trois causes, toutes hors du programme mesuré :

• la machine fait autre chose en même temps — le temps mesuré n'est pas tout entier consacré au tri ;
• les petites tailles sont dominées par des coûts fixes (appel de fonction, copie du tableau) qui n'ont rien de quadratique ; c'est pourquoi le premier rapport, $5,16$, est le plus faux ;
• la mémoire cache change de comportement selon la taille des données, par paliers.

La règle de méthode. Compter pour identifier la loi, chronométrer pour savoir si c'est utilisable. Le comptage est reproductible d'une machine à l'autre et se compare à une formule ; le temps répond à la seule question que le comptage ne traite pas — « est-ce assez rapide pour mon usage ? ». Prendre le meilleur de plusieurs exécutions, comme ci-dessus, réduit le bruit sans le supprimer.