Le tri par sélection est-il stable

Il ne l'est pas. Le contre-exemple le plus court se trouve en essayant tous les tableaux de longueur croissante sur deux valeurs seulement :

t = [(1, 0), (1, 1), (0, 2)]        # (valeur, rang d'arrivée)
tri_selection_cle(t)                # trie sur la première composante
# obtenu : [(0, 2), (1, 1), (1, 0)]
# stable  : [(0, 2), (1, 0), (1, 1)]

Trois éléments, deux valeurs distinctes : on ne peut pas faire plus court. Les rangs $0$ et $1$ sont sortis dans l'ordre inverse.

Pourquoi. C'est l'échange qui est en cause. Au tour $0$, le minimum est le $(0,2)$ final ; l'échanger avec la case $0$ y envoie le $(1,0)$ qui s'y trouvait — d'un bond, par-dessus le $(1,1)$. Un échange déplace deux éléments, dont un qui n'avait rien demandé, et il peut le faire sauter par-dessus ses ex æquo.

La variante stable. On remplace l'échange par un décalage du bloc : l'élu remonte d'une case à la fois, et les autres glissent d'un cran sans se dépasser.

def tri_selection_stable(t):
    """Tri par sélection stable : décalage au lieu d'échange."""
    n = len(t)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if t[j][0] < t[m][0]:
                m = j
        x = t[m]
        for k in range(m, i, -1):      # le bloc glisse d'un cran
            t[k] = t[k - 1]
        t[i] = x

Sur le contre-exemple : [(0, 2), (1, 0), (1, 1)] — l'ordre d'arrivée est respecté. Validation : comparée à sorted(t, key=...), qui est stable, sur $2000$ tableaux tirés au hasard — $2000$ cas passent.

Le prix. Les comparaisons ne changent pas : toujours $n(n-1)/2$. Mais les écritures passent de $n-1$ échanges — soit $3(n-1)$ affectations — à un décalage qui peut faire $n-1$ écritures par tour, donc jusqu'à $n(n-1)/2$ en tout. On a acheté la stabilité avec des écritures, et sur une mémoire où écrire coûte cher, le marché n'est pas toujours bon. C'est exactement le compromis qui fait qu'en pratique on préfère le tri par insertion, stable sans rien payer de plus.