Le tri de Python est-il stable — c'est-à-dire respecte-t-il l'ordre…

L'expérience. On numérote les lignes avant de trier, puis on vérifie que, dans chaque groupe de clé égale, les numéros restent croissants.

import random
random.seed(9)
for _ in range(500):
    n = random.randint(0, 20)
    t = [{"c": random.randint(0, 2), "rang": i} for i in range(n)]
    s = sorted(t, key=lambda l: l["c"])
    for c in (0, 1, 2):
        rangs = [l["rang"] for l in s if l["c"] == c]
        assert rangs == sorted(rangs)

$500$ cas passent : le tri de Python est stable. Sur l'exemple à la main — Zoe, Ana, Bob, Yan, Ali, avec les classes 1G1, 1G3, 1G1, 1G3, 1G1 — le tri par classe rend Zoe, Bob, Ali, Ana, Yan : dans chaque classe, l'ordre d'arrivée est conservé.

À quoi cela sert. À trier sur deux colonnes en deux temps : trier d'abord sur la clé secondaire, puis sur la clé principale. La stabilité garantit que le second tri ne défait pas le premier. C'est une alternative au p-uplet du cours, et la seule voie possible quand la seconde clé n'est pas numérique — on ne peut pas écrire -ligne["nom"].

Ce que l'expérience ne prouve pas. $500$ tirages ne sont pas une preuve ; ils écartent l'hypothèse « le tri n'est pas stable », ils ne démontrent pas qu'il l'est. Ici la garantie vient d'ailleurs : la documentation de Python l'affirme. Une expérience confirme une promesse, elle ne la remplace pas.