Les tris

Invariant ${\mathcal{I}}_i$ : « $t[\mathrm{0..}i-1]$ est trié et ses éléments sont inférieurs ou égaux à tous ceux de $t[i..n-1]$ ». Initialisation : préfixe vide. Conservation : la boucle interne calcule l'indice du minimum de $t[i..n-1]$ (invariant du chapitre 2) ; l'échange place ce minimum en position $i$ — il majore le préfixe (par ${\mathcal{I}}_i$) et minore le reste : ${\mathcal{I}}_{i+1}$. À la sortie ($i=n-1$), le préfixe $t[\mathrm{0..}n-2]$ est trié et minore $t[n-1]$ : tout est trié, et l'on n'a fait qu'échanger des éléments de $t$ — permutation garantie.

Invariant externe : « $t[\mathrm{0..}i-1]$ est trié ». La boucle interne décale vers la droite les éléments du préfixe strictement supérieurs à $x$ — son propre invariant : « $t[j+\mathrm{1..}i]$ contient les éléments déplacés, tous $>x$, et $t[\mathrm{0..}j-1]$ n'a pas bougé » ; son variant : $j$. À l'arrêt, soit $j=0$, soit $t[j-1]\le x$ : poser $x$ en $j$ redonne un préfixe $t[\mathrm{0..}i]$ trié. Aucun élément n'est perdu : $x$ est sauvegardé avant les décalages et reposé — la permutation est préservée.

Récurrence forte sur $n$ (chapitre 6). Base : une liste de taille $\le 1$ est triée. Hérédité : les deux appels portent sur des listes strictement plus courtes (pour $n\ge 2$, $1\le m\le n-1$ : variant) ; par hypothèse ils renvoient des permutations triées des deux moitiés ; la fusion de deux listes triées est triée et contient exactement leurs éléments — le résultat est une permutation triée de $t$.

C'est l'argument de la dichotomie (chapitre 5, exercice 9), à plus grande échelle. Un tri par comparaisons doit distinguer les $n!$ ordres initiaux possibles : deux permutations différentes de l'entrée exigent des suites de mouvements différentes, donc des suites de réponses aux comparaisons différentes. Après $k$ comparaisons (chacune binaire), l'algorithme ne distingue qu'au plus $2^k$ scénarios : il faut $2^k\ge n!$, soit $k\ge {\log }_2(n!)$. Or

$${\log }_2(n!)=\sum _{i=2}^n{\log }_{2}i\ge \frac{n}{2}{\log }_2\frac{n}{2},$$

(en minorant les $n/2$ derniers termes par ${\log }_2(n/2)$) : c'est bien de l'ordre de $n\log n$. (La frontière $O(n\log n)$ est donc dans le problème, pas dans nos algorithmes — comme les $2^n-1$ déplacements de Hanoï. Et l'évasion du tri par comptage s'explique : en lisant la valeur des éléments, il obtient bien plus qu'un bit par opération.)

Sélection : $i=0$ : minimum de $[4,2,5,1]$ en position $3$, échange $\to [1,2,5,4]$ ($3$ comparaisons). $i=1$ : minimum de $[2,5,4]$ déjà en place $\to$ inchangé ($2$ comp.). $i=2$ : minimum de $[5,4]$ en position $3$, échange $\to [1,2,4,5]$ ($1$ comp.). Total : $6$ comparaisons, $2$ échanges effectifs.

Insertion : $i=1$ : insérer $2$ dans $[4]$ $\to [2,4,5,1]$ ($1$ comp.). $i=2$ : insérer $5$ dans $[2,4]$ — reste en place ($1$ comp.). $i=3$ : insérer $1$ dans $[2,4,5]$ — traverse tout $\to [1,2,4,5]$ ($3$ comp.). Total : $5$ comparaisons.

Sur ce petit exemple l'insertion gagne d'une comparaison — et l'écart se creuse sur les tableaux presque triés, où la sélection s'obstine à ses $\frac{n(n-1)}{2}$. (Le déroulé manuel, vérification d'invariant comprise — le préfixe trié grandit bien d'un cran par étape — reste le premier test de tout tri.)

$(i,j)=(0,0)$ : $1\le 2$, $r=[1]$ ; $(1,0)$ : $4>2$, $r=[1,2]$ ; $(1,1)$ : $4>3$, $r=[1,2,3]$ ; $(1,2)$ : $4\le 9$, $r=[1,2,3,4]$ ; $(2,2)$ : $7\le 9$, $r=[1,2,3,4,7]$ ; $i=3$ : la liste $a$ est épuisée, on colle $b[2:]=[9]$ — résultat $[1,2,3,4,7,9]$, $5$ comparaisons. En général : chaque comparaison place exactement un élément, et la dernière place l'avant-dernier au pire — soit au plus $a+b-1$ comparaisons, atteint quand les deux listes s'entrelacent jusqu'au bout (comme ici : $5=3+3-1$). (Et au mieux $\min (a,b)$, atteint quand la liste la plus courte précède entièrement l'autre : la boucle s'arrête dès l'épuisement de la première.)

Tri stable attendu : $[(\text{Alice},12),(\text{Chloe},12),(\text{Bob},15)]$ — Alice avant Chloé, comme au départ.

Sélection sur les notes $[12,15,12]$ : à $i=0$, le minimum ($12$) est déjà en position $0$ — pas d'échange. À $i=1$ : le minimum de $[(\text{Bob},15),(\text{Chloe},12)]$ est Chloé, échange avec Bob $\to [(\text{Alice},12),(\text{Chloe},12),(\text{Bob},15)]$. Ici, par chance, le résultat est stable ! Le contre-exemple demande que l'échange enjambe un égal : prenons $[(\text{Bob},15),(\text{Alice},12),(\text{Chloe},15)]$. À $i=0$, le minimum est Alice : échange avec Bob $\to [(\text{Alice},12),(\text{Bob},15)\dots ]$ — non : $\to [(\text{Alice},12),(\text{Bob},15),(\text{Chloe},15)]$ ? L'échange envoie Bob en position $1$… où il était déjà relativement à Chloé. Troisième essai, l'exemple canonique : $[(\text{Bob},15),(\text{Chloe},15),(\text{Alice},12)]$. À $i=0$ : minimum Alice (position $2$), échange avec Bob $\to [(\text{Alice},12),(\text{Chloe},15),(\text{Bob},15)]$ — Bob est passé derrière Chloé : les deux $15$ ont été inversés, et plus rien ne les remettra dans l'ordre. Le tri par sélection n'est pas stable, et le mécanisme est identifié : le grand échange à longue distance enjambe les égaux. (Chercher un contre-exemple est une compétence en soi : les deux premières tentatives échouent et c'est instructif — il faut que l'élément échangé saute par-dessus son égal, d'où la configuration minimale à trois fiches.)

L'arbre : une liste de $16$, deux de $8$, quatre de $4$, huit de $2$, seize de $1$ — ${\log }_{2}16=4$ niveaux de découpe, et les fusions remontent : huit fusions de tailles $1+1$, quatre de $2+2$, deux de $4+4$, une de $8+8$. Chaque niveau fusionne $16$ éléments au total : travail $\approx 16$ par niveau, $4$ niveaux, $\approx 64$ placements (et au plus $16\times 4-15=49$ comparaisons). Le chronométrage typique donne des temps quasi proportionnels à $n$ à un facteur logarithmique près : de $10^4$ à $10^6$, $n$ est multiplié par $100$ et le temps par $\approx 130$ — le facteur supplémentaire $\approx 1,3$ est le rapport $\log (10^6)/\log (10^4)=1,5$ atténué par les constantes. (L'arbre est la bonne image mentale : « combien de niveaux, combien par niveau » résout toutes les récurrences de ce cours sans aucune machinerie.)

Sur $[1,2,\dots ,n]$ : le pivot $1$ donne $\text{petits}=[]$ et $\text{grands}=[2,\dots ,n]$ ($n-1$ comparaisons) ; l'appel récursif sur les grands recommence avec le pivot $2$, etc. — total $(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$ : l'arbre est un chemin, le tri est quadratique sur l'entrée la plus courante du monde réel (les données déjà triées ou presque). Le tableau décroissant donne le symétrique exact ($\text{grands}=[]$) : même compte. Avec un pivot uniforme au hasard, chaque exécution a une petite probabilité de mal tomber partout — l'espérance du coût est $O(n\log n)$ (admis), et la probabilité d'un comportement quadratique devient infinitésimale ; mais pour toute stratégie de pivot, il existe une entrée défavorable (au hasard près) : le pire cas théorique reste $O(n^2)$. (D'où la formulation soignée du cours : « $O(n\log n)$ en moyenne et en pratique, $O(n^2)$ au pire » — les deux moitiés de la phrase sont vraies ensemble, et confondre les deux mesures est l'erreur classique sur le tri rapide.)

fiches = [("Bob", 15), ("Alice", 12), ("Chloe", 15), ("Dan", 12)]

# 1. une seule clé composite : note décroissante = -note croissante
r1 = sorted(fiches, key=lambda f: (-f[1], f[0]))

# 2. deux tris STABLES successifs : critère secondaire D'ABORD
r2 = sorted(fiches)                                    # alphabétique
r2 = sorted(r2, key=lambda f: f[1], reverse=True)      # puis par note

assert r1 == r2 == [("Bob", 15), ("Chloe", 15), ("Alice", 12), ("Dan", 12)]

La méthode 2 repose entièrement sur la stabilité de sorted : le second tri, en regroupant les notes égales, conserve l'ordre alphabétique établi par le premier. L'ordre des deux tris est contre-intuitif — le critère secondaire d'abord, le principal ensuite — et c'est le pattern historique du tri de fichiers multi-critères (et du tri par base de l'exercice 9). (Avec un tri non stable, la méthode 2 s'effondre silencieusement : la stabilité n'est pas une coquetterie de théoricien, c'est une fonctionnalité.)

import random, time

def valide(tri_renvoie, essais=500):
    random.seed(9)
    for _ in range(essais):
        t = [random.randint(0, 50) for _ in range(random.randint(0, 40))]
        copie = list(t)
        r = tri_renvoie(t)
        assert all(r[i] <= r[i+1] for i in range(len(r) - 1))
        assert sorted(copie) == r and t == copie     # permutation, source intacte

def chrono(tri_renvoie, t):
    debut = time.perf_counter()
    tri_renvoie(list(t))
    return time.perf_counter() - debut

n = 2000
profils = {"aleatoire": [random.randint(0, 10**6) for _ in range(n)],
           "triee":     list(range(n)),
           "inverse":   list(range(n, 0, -1))}

Résultats typiques (ordres de grandeur, machine ordinaire) :

Le tableau est le cours : l'insertion et les bulles voient le tri préexistant, la sélection non ; la fusion garantit ; le rapide naïf s'effondre précisément sur les entrées ordonnées (exercice 5) ; le comptage, hors catégorie, ne compare pas. (Un banc unique, six algorithmes, trois profils : c'est la « caractérisation expérimentale » que demande le programme — et chaque case surprenante du tableau a son théorème au chapitre.)

def tri_et_inversions(t: list) -> tuple:
    """Renvoie (liste triée, nombre d'inversions de t)."""
    if len(t) <= 1:
        return (list(t), 0)
    m = len(t) // 2
    a, inv_a = tri_et_inversions(t[:m])
    b, inv_b = tri_et_inversions(t[m:])
    r, i, j, inv = [], 0, 0, inv_a + inv_b
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i]); i += 1
        else:
            r.append(b[j]); j += 1
            inv += len(a) - i        # b[j] est plus petit que TOUT le reste de a
    return (r + a[i:] + b[j:], inv)

assert tri_et_inversions([2, 4, 1, 3])[1] == 3     # (2,1), (4,1), (4,3)

Justification : toute inversion $(x,y)$ de $t$ ($x$ avant $y$, $x>y$) est comptée exactement une fois — soit ses deux membres tombent dans la même moitié (comptée récursivement dans inv_a ou inv_b), soit $x$ est à gauche et $y$ à droite, et elle est comptée au moment précis où $y=b[j]$ est prélevé avant les éléments restants de $a$ (tous $>y$, et tous avant $y$ dans $t$) : le terme len(a) - i. Le surcoût par fusion est $O(1)$ par prélèvement : le coût total reste $O(n\log n)$. Pour $n=10^5$ éléments, le compte passe de $\sim 5\cdot 10^9$ opérations (chapitre 3) à $\sim 2\cdot 10^6$. (Greffer un calcul sur un algorithme existant en exploitant son invariant — « $a$ et $b$ sont triés, et tout $a$ précède tout $b$ dans l'original » — est un geste de conception majeur : l'algorithme devient un échafaudage réutilisable.)

def tri_comptage_stable(fiches: list, cle, k: int) -> list:
    """Trie les fiches selon cle(f) dans [0, k-1], en respectant l'ordre initial
    des égaux. Coût O(n + k)."""
    effectifs = [0] * k
    for f in fiches:
        effectifs[cle(f)] += 1
    debut = [0] * k                      # position de départ de chaque valeur
    for v in range(1, k):
        debut[v] = debut[v - 1] + effectifs[v - 1]
    r = [None] * len(fiches)
    for f in fiches:                     # parcours DANS L'ORDRE INITIAL
        r[debut[cle(f)]] = f
        debut[cle(f)] += 1
    return r

def tri_par_base(t: list) -> list:
    """Trie des entiers de [0, 999] par trois passes de comptage stable."""
    r = tri_comptage_stable(t, lambda x: x % 10, 10)          # unités
    r = tri_comptage_stable(r, lambda x: (x // 10) % 10, 10)  # dizaines
    return tri_comptage_stable(r, lambda x: x // 100, 10)     # centaines

assert tri_par_base([329, 457, 657, 839, 436, 720, 355]) \
       == [329, 355, 436, 457, 657, 720, 839]

La stabilité porte tout l'édifice : après la passe des dizaines, deux nombres de même chiffre des dizaines restent rangés par unités (la passe précédente) — par récurrence, après la passe $j$, le tableau est trié selon les $j$ derniers chiffres. Avec une passe instable, l'information des passes antérieures serait détruite et le résultat faux (tester en remplaçant par la version non stable du cours : le banc de l'exercice 7 le détecte aussitôt). Coût : $d$ passes en $O(n+10)$ pour des nombres à $d$ chiffres — $O(d\cdot n)$, linéaire à $d$ fixé : c'est ainsi que les cartes perforées furent triées un siècle durant. (Le critère secondaire d'abord, le principal en dernier : exactement le pattern des fiches de l'exercice 6, industrialisé.)

Majoration : $n!=1\cdot 2\cdots n\le n^n$, d'où ${\log }_2(n!)\le n{\log }_{2}n$. Minoration : les $n/2$ facteurs supérieurs valent chacun au moins $n/2$, donc $n!\ge (n/2{)}^{n/2}$ et ${\log }_2(n!)\ge \frac{n}{2}{\log }_2\frac{n}{2}$. (L'encadrement exact, ${\log }_2(n!)=n{\log }_{2}n-n{\log }_{2}e+O(\log n)$, est la formule de Stirling du cours de mathématiques — notre version élémentaire suffit à l'asymptotique.)

Pour $n=100$ : ${\log }_2(100!)={\sum }_{i=2}^{100}{\log }_{2}i\approx 525$ (calcul direct : sum(math.log2(i) for i in range(2, 101)) donne $524,8$). Toute stratégie de tri par comparaisons admet donc une entrée à $\ge 525$ comparaisons. Le tri fusion sur $n=100$ en effectue au plus $n\lceil {\log }_{2}n\rceil -2^{\lceil {\log }_{2}n\rceil }+1=100\times 7-128+1=573$ — soit moins de $10\%$ au-dessus de la borne absolue : la borne est remarquablement serrée, et le tri fusion remarquablement proche de l'optimal, pas seulement en ordre de grandeur mais presque en constante. (Une borne inférieure qui colle à un algorithme réel à $10\%$ près : le problème du tri est, à ce titre, l'un des mieux compris de l'informatique — et la marge restante a nourri cinquante ans de raffinements, dont le Timsort de Python.)