Compter les inversions

def nb_inversions(t: list) -> int:
    c = 0
    for i in range(len(t)):
        for j in range(i + 1, len(t)):
            if t[i] > t[j]:
                c += 1
    return c

Démonstration :

1. Le tri à bulles n'échange que des éléments adjacents mal ordonnés $t[i]>t[i+1]$. Un tel couple constitue une inversion.
2. L'échange de $t[i]$ et $t[i+1]$ transforme cette paire ordonnée de façon croissante. L'inversion disparait.
3. Cet échange d'éléments adjacents ne modifie pas la position relative de ces deux éléments par rapport au reste du tableau (tout autre élément garde la même relation d'ordre avec $t[i]$ et $t[i+1]$).
4. Chaque échange diminue le nombre d'inversions du tableau d'exactement 1.
5. Le tableau est trié si et seulement si son nombre d'inversions est nul. Le nombre total d'échanges est donc égal au nombre d'inversions initial.