Modifier tri insertion pour trier par ordre décroissant

Un seul caractère. Le > de la condition devient < :

def tri_insertion_decroissant(t):
    """Trie t par ordre DÉCROISSANT, sur place."""
    for i in range(1, len(t)):
        x = t[i]
        j = i
        while j > 0 and t[j - 1] < x:      # SEULE modification : > devient <
            t[j] = t[j - 1]
            j = j - 1
        t[j] = x

tri_insertion_decroissant([5, 2, 8, 1]) rend [8, 5, 2, 1]. Validation : comparée à sorted(t, reverse=True) sur $2000$ tableaux tirés au hasard, doublons compris — $2000$ cas passent.

L'invariant change, mais d'un mot. Il devient : avant le tour $i$, t[0..i-1] est trié par ordre décroissant et contient les mêmes éléments que les $i$ premiers du tableau initial. La structure de la démonstration — initialisation, conservation, terminaison — ne bouge pas d'une ligne ; seul le sens de la relation d'ordre est renversé.

Le variant, lui, ne change pas du tout. C'est toujours j, entier, positif, strictement décroissant. La terminaison ne dépend pas du sens du tri : elle ne dépend que de la façon dont j évolue.

Ce que cet exercice enseigne. Un invariant bien écrit se transporte. Il est paramétré par la relation d'ordre, et changer la relation ne demande pas de tout redémontrer. C'est un critère de qualité : un invariant qu'il faudrait réécrire entièrement pour une variante aussi mince était sans doute trop lié au code et pas assez à l'idée.