Écrire la partition : ranger un tableau autour d'un pivot, les plus…

def partition(t, g, d):
    """Range t[g..d] autour du pivot t[d]. Rend l'indice final du pivot.

    Précondition  : g <= d, indices valides.
    Postcondition : en notant p le résultat, t[k] <= t[p] pour g <= k < p
                    et t[k] >= t[p] pour p < k <= d.
    """
    pivot = t[d]
    i = g
    for j in range(g, d):
        if t[j] <= pivot:
            t[i], t[j] = t[j], t[i]
            i = i + 1
    t[i], t[d] = t[d], t[i]
    return i

L'invariant à trois zones. Avant le tour $j$, le tableau t[g..d-1] est découpé en trois :

• t[g..i-1] : les éléments $\le$ pivot, déjà rangés à gauche ;
• t[i..j-1] : les éléments $>$ pivot, rejetés à droite de la frontière ;
• t[j..d-1] : pas encore regardés.

C'est le même schéma que les invariants du cours, avec une frontière de plus. Deux indices avancent : $j$ à chaque tour, $i$ seulement quand on range un petit élément.

Conservation. Si t[j] $\le$ pivot, l'échange l'envoie en position $i$ — et renvoie en position $j$ l'élément qui y était, forcément $>$ pivot puisqu'il appartenait à la deuxième zone. Les trois zones restent conformes. Sinon, on ne fait rien : t[j] rejoint naturellement la deuxième zone quand $j$ avance.

Terminaison. À la sortie, $j=d$ : la troisième zone est vide. L'échange final place le pivot en position $i$, à la frontière exacte des deux autres.

Contrôle. partition([5, 2, 8, 1, 9, 3], 0, 5) rend $2$, et le tableau devient [2, 1, 3, 5, 9, 8] : à gauche du $3$, on trouve $2$ et $1$ ; à droite, $5$, $9$, $8$. La postcondition entière, plus la préservation du contenu, a été vérifiée sur $3000$ tableaux tirés au hasard.

Pourquoi cette fonction compte. Répétée sur les deux moitiés qu'elle sépare, elle est le tri rapide de Hoare — l'algorithme cité dans le repère historique du chapitre. Un tri complet en $n{\log }_{2}n$ en moyenne tient donc dans cette boucle plus deux appels récursifs. C'est un travail de terminale, mais la brique, elle, se comprend dès maintenant : elle ne demande qu'un invariant à trois zones.