Voici une version fautive du tri par sélection

def tri_selection_bug(t):
    n = len(t)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if t[j] < t[m]:
                m = j
                t[i], t[m] = t[m], t[i]     # <- ECHANGE PREMATURE
    return t

Le plus petit contre-exemple : [2, 0, 1]. On l'obtient en essayant tous les tableaux de longueur $2$, puis $3$, sur un petit alphabet de valeurs :

from itertools import product
for n in range(2, 6):
    for vals in product(range(4), repeat=n):
        c = list(vals)
        tri_selection_bug(c)
        if c != sorted(vals):
            print(vals, "->", c, "au lieu de", sorted(vals)); break
# (2, 0, 1) -> [1, 0, 2] au lieu de [0, 1, 2]

Trois éléments suffisent, et le résultat [1, 0, 2] n'est même pas trié.

**Quelle étape échoue : la conservation. La démonstration du cours dit : « la boucle interne calcule l'indice m d'un plus petit élément de t[i..n-1] ». Cette phrase suppose que le tableau ne bouge pas** pendant la boucle interne — c'est l'invariant de indice_maximum, appliqué à un sous-tableau, et il porte sur un tableau fixe. Ici l'échange déplace des éléments sous la boucle qui les examine : à la fin, t[m] n'est plus l'élément que m désignait quand on l'a choisi. L'invariant de la boucle interne est faux, donc celui de la boucle externe ne se conserve pas.

Ce que l'exercice montre. Un jeu de tests malchanceux ne l'aurait pas vu : sur [5, 2, 8, 1], cette version fautive rend le bon résultat. Il faut $2$, $0$, $1$ dans cet ordre précis. **La démonstration, elle, désigne l'erreur *et son endroit*** — c'est l'étape de conservation qui refuse de passer, et elle refuse à la ligne près.

Une remarque annexe. Si l'on écrit if t[j] < t[i]: t[i], t[j] = t[j], t[i] sans variable m, on obtient un algorithme correct — un « tri par échanges », vérifié sur $2000$ tirages — mais qui fait $45$ échanges sur un tableau de $10$ éléments à l'envers, contre $9$ pour le tri par sélection. Correct, et quatre fois plus coûteux en écritures.