Écrire le tri à bulles

def tri_bulles(t):
    """Trie t en échangeant les voisins mal ordonnés."""
    n = len(t)
    for i in range(n - 1):
        # invariant : t[n-i..n-1] est trié et contient les i plus grands
        for j in range(n - 1 - i):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]

def tri_bulles_drapeau(t):
    """Même chose, mais on s'arrête dès qu'un passage n'échange rien."""
    n = len(t)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]
                echange = True
        if not echange:
            break

Validation : $2000$ tableaux tirés au hasard, les deux versions d'accord avec sorted.

L'invariant. Après le passage $i$, les $i$ plus grands éléments sont à leur place définitive, en queue de tableau. Chaque passage fait « remonter » le plus grand élément restant jusqu'au bout, par échanges de proche en proche — d'où le nom.

La mesure.

Sur un tableau déjà trié, le drapeau fait tomber le coût de $79800$ à $399$ : le premier passage n'échange rien, on sort. Le tri devient linéaire dans son meilleur cas — comme le tri par insertion, et pour la même raison. Sur un tableau à l'envers, en revanche, rien n'est gagné : $n(n-1)/2$, avec un rapport de $4,0$ à chaque doublement.

Pourquoi il n'est pas au programme. Il est quadratique comme les deux autres, mais il fait beaucoup plus d'échanges — un par inversion, contre $n-1$ pour la sélection. Il est célèbre surtout pour être le plus mauvais des tris simples ; le programme lui préfère, à juste titre, les deux qui se démontrent le plus clairement.