Boucles imbriquées et complexité quadratique

Lemme (la bulle remonte). Après une passe complète de la boucle interne sur $t[\mathrm{0..}q]$, le maximum de $t[\mathrm{0..}q]$ se trouve en position $q$. En effet, considérons la première position $j$ où se trouve ce maximum : dès que $i$ atteint $j$, le test échange (ou laisse) le maximum en $i+1$, et il sera entraîné par tous les échanges suivants — un mini-invariant de la boucle interne : « après le tour $i$, $t[i+1]$ est le maximum de $t[\mathrm{0..}i+1]$ ».

Invariant de la boucle externe. ${\mathcal{I}}_k$ : « $t[n-k..n-1]$ contient les $k$ plus grands éléments du tableau, triés et à leur place définitive ». Initialisation : $k=0$, suffixe vide. ✓ Conservation : la passe $k$ travaille sur $t[\mathrm{0..}n-1-k]$ et, par le lemme, amène son maximum en position $n-1-k$ ; ce maximum est inférieur ou égal à tous les éléments du suffixe déjà classé, donc le suffixe trié s'étend d'une case. ✓ Après $n-1$ passes, $t[\mathrm{1..}n-1]$ est trié et contient les $n-1$ plus grands : $t[0]$, le minimum, est aussi à sa place — le tableau est trié. La terminaison est immédiate (deux boucles for).

(a) $10n$ exécutions : la boucle interne est de longueur constante — coût $O(n)$, linéaire malgré les deux for.

(b) ${\sum }_{i=0}^{n-1}i=\frac{n(n-1)}{2}$ : le triangle strict — $O(n^2)$.

(c) ${\sum }_{i=0}^{n-1}(n-i)=n+(n-1)+\cdots +1=\frac{n(n+1)}{2}$ : le triangle avec diagonale — $O(n^2)$ aussi. (Les trois réponses tiennent en une règle : sommer la longueur de la boucle interne sur toutes les valeurs de $i$ — l'asymptotique tombe ensuite toute seule.)

def tous_distincts(t: list) -> bool:
    for i in range(len(t)):
        for j in range(i + 1, len(t)):
            # Invariant : aucun couple examiné avant (i, j) n'est un doublon
            if t[i] == t[j]:
                return False
    return True

Correction : si la fonction renvoie False, elle vient d'exhiber $i<j$ avec $t[i]=t[j]$ : il y a bien un doublon. Si elle renvoie True, les deux boucles ont épuisé tous les couples $i<j$ sans en trouver : l'invariant final dit qu'aucun doublon n'existe. La borne range(i + 1, ...) est essentielle : avec range(len(t)), le couple $j=i$ donnerait $t[i]=t[i]$ et la fonction répondrait toujours False.

Coût : $\frac{n(n-1)}{2}$ comparaisons au pire (tableau sans doublon) : $O(n^2)$. La version dictionnaire (a_un_doublon, chapitre 2) fait le même travail en $O(n)$ — mais exige des éléments utilisables comme clés ; la double boucle, elle, ne demande que l'égalité. (Quand les deux outils s'appliquent, le dictionnaire gagne ; savoir écrire et prouver la double boucle reste le socle.)

Il suffit de ne plus s'arrêter à la première trouvaille :

def positions_facteur(m: str, s: str) -> list:
    pos = []
    for i in range(len(s) - len(m) + 1):
        j = 0
        while j < len(m) and s[i + j] == m[j]:
            j += 1
        if j == len(m):
            pos.append(i)
    return pos

assert positions_facteur("aa", "aaaa") == [0, 1, 2]    # chevauchements comptés !
assert positions_facteur("ana", "banane") == [1, 3]
assert positions_facteur("x", "banane") == []

Le test "aaaa" illustre le choix de contrat : les occurrences aux positions $0$, $1$, $2$ se chevauchent, et notre spécification les compte toutes — l'autre convention (reprendre la recherche après l'occurrence trouvée, donnant $[0,2]$) existe aussi ; l'énoncé doit trancher. Coût inchangé : $O(np)$. (Transformer un « premier trouvé » en « tous trouvés » : remplacer le return par un append — un geste de refactorisation à connaître.)

Passe $k=0$ (sur $t[\mathrm{0..3}]$, $3$ comparaisons) : $5>1$, échange $\to [1,5,4,2]$ ; $5>4$, échange $\to [1,4,5,2]$ ; $5>2$, échange $\to [1,4,2,5]$. Invariant : $t[\mathrm{3..3}]=[5]$, le plus grand, en place. ✓

Passe $k=1$ ($2$ comparaisons) : $1<4$, rien ; $4>2$, échange $\to [1,2,4,5]$. Invariant : $t[\mathrm{2..3}]=[4,5]$, les deux plus grands, triés. ✓

Passe $k=2$ ($1$ comparaison) : $1<2$, rien. Invariant : $t[\mathrm{1..3}]=[2,4,5]$. ✓ — et $t[0]=1$ est le minimum : trié.

Total : $3+2+1=6$ comparaisons (c'est $\frac{4\times 3}{2}$, conforme), $4$ échanges. (Dérouler un algorithme à la main sur un petit exemple en vérifiant l'invariant à chaque étape : le meilleur test qui soit avant même d'allumer la machine.)

Aucun échange $\Rightarrow$ trié. Si la passe n'a rien échangé, c'est que chaque test a constaté $t[i]\le t[i+1]$, pour tout $i$ parcouru. Or « chaque voisin en ordre » entraîne « tout en ordre » : pour $i<j$, $t[i]\le t[i+1]\le \cdots \le t[j]$ par transitivité — le tableau est croissant.

Variant. La quantité $v=(n-1)-k$ convient : tant que la boucle tourne, le tableau n'est pas encore certifié trié et $k\le n-1$ (après $n-1$ passes, l'invariant du cours garantit le tri, donc une passe sans échange, donc l'arrêt) ; et $k$ augmente de $1$ à chaque tour, donc $v$ décroît strictement. La boucle while termine en au plus $n$ passes. (Le drapeau echange transforme une propriété mathématique — « plus rien à faire » — en condition d'arrêt observable : c'est tout l'art des boucles while bien construites.)

L'astuce anti-cube : pour $i$ fixé, la somme de $t[i..j]$ se déduit de celle de $t[i..j-1]$ en ajoutant $t[j]$ — la somme s'accumule le long de la boucle interne :

def meilleure_tranche(t: list) -> float:
    """Précondition : t non vide."""
    meilleur = t[0]
    for i in range(len(t)):
        s = 0
        for j in range(i, len(t)):
            s += t[j]              # Invariant interne : s = somme de t[i..j]
            if s > meilleur:
                meilleur = s
    return meilleur

assert meilleure_tranche([2, -8, 3, -2, 4, -10]) == 5
assert meilleure_tranche([-3, -1, -7]) == -1       # tout négatif : la moins mauvaise case

La version naïve à trois étages — pour chaque couple $(i,j)$, recalculer la somme par une troisième boucle — coûterait $O(n^3)$ ; l'accumulation la ramène à $O(n^2)$. Le second test garde la spécification honnête : « tranche non vide » signifie qu'un tableau tout négatif rend son plus grand élément, pas $0$. (Il existe un algorithme linéaire — Kadane — hors programme : la version quadratique propre est le livrable attendu.)

import random

for essai in range(1000):
    t = [random.randint(-20, 20) for _ in range(random.randint(0, 15))]
    copie = list(t)               # référence intacte (tri en place !)
    tri_bulles(t)
    assert all(t[i] <= t[i + 1] for i in range(len(t) - 1)), f"non trie : {t}"
    assert sorted(copie) == t, f"elements modifies : {copie} -> {t}"

La faute d'échange typique est t[i] = t[i + 1] puis t[i + 1] = t[i] (sans variable temporaire ni affectation simultanée) : la première écriture détruit $t[i]$, et le tableau final contient un doublon venu de nulle part — il peut être parfaitement croissant, donc la première assertion passe, mais sorted(copie) == t échoue. La forme assert condition, message (hors annexe du programme, fournie avec sa documentation) affiche le tableau fautif dès qu'un essai échoue. Noter aussi la copie avant l'appel : le tri étant en place, sans elle on comparerait le résultat à lui-même. (Tester une fonction mutante exige de photographier l'entrée d'abord — l'oubli classique qui rend un test toujours vert.)

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

(b) d'abord : « trié » signifie $t[i]\le t[j]$ pour tous $i<j$, c'est-à-dire zéro inversion — équivalence par définition.

(a) Chaque échange du tri à bulles porte sur deux voisins mal ordonnés $t[i]>t[i+1]$ : il corrige l'inversion $(i,i+1)$, et ne modifie l'ordre relatif d'aucun autre couple (tout autre élément reste du même côté des deux échangés, ou des deux à la fois). Le nombre d'inversions diminue donc d'exactement $1$ par échange. À la fin, il vaut $0$ par (b) : le nombre total d'échanges est le nombre initial d'inversions. (Joli sous-produit : le nombre d'inversions est un variant naturel du tri à bulles — il prouve à lui seul que l'algorithme avec drapeau termine, et mesure le « désordre » d'un tableau ; le tri à bulles est lent parce qu'il ne détruit qu'une inversion par échange, quand un tableau peut en contenir $\frac{n(n-1)}{2}$.)

Prenons $s={\text{a}}^n$ (la lettre a répétée $n$ fois) et $m={\text{a}}^{p-1}\text{b}$ (des a, puis un b final). À chaque position de départ $i\le n-p$, la boucle interne lit $p-1$ coïncidences (a contre a) puis une discordance sur le b : exactement $p$ comparaisons, et l'échec n'arrive qu'à la toute fin. Nombre total :

$$(n-p+1)\times p$$

comparaisons — pour $p=n/2$, cela fait $(\frac{n}{2}+1)\frac{n}{2}\sim \frac{n^2}{4}$ : le comportement quadratique est atteint, pas seulement majoré. (Construire l'entrée adverse est l'autre moitié de l'analyse : la borne $O$ majore, l'exemple méchant prouve qu'on ne peut pas annoncer mieux. Les algorithmes de recherche rapide — Boyer-Moore, Knuth-Morris-Pratt, hors programme — sont nés précisément de ces entrées répétitives : ils mémorisent ce que la version naïve oublie, à savoir que les caractères déjà lus sont connus.)

Petits pas vers la gauche. Pendant une passe, l'indice $i$ avance de gauche à droite. Un élément ne se déplace vers la gauche que s'il est le plus petit des deux comparés, c'est-à-dire lors de l'unique comparaison où il est en position $i+1$ : il recule alors d'une case, puis l'indice $i$ le dépasse et ne le touchera plus de la passe. Un recul par passe, au maximum. (Vers la droite, en revanche, un grand élément peut être entraîné sur toute la passe — c'est la « bulle ».)

Conséquence. Si le minimum est en position $n-1$, il doit reculer de $n-1$ cases pour atteindre sa place : il faut $n-1$ passes, et le drapeau ne s'éteint jamais avant — sur $[2,3,4,\dots ,n,1]$, un tableau « presque trié » (une seule valeur mal placée !), le tri à bulles est aussi lent que sur un tableau quelconque : $O(n^2)$ comparaisons.

Le tri shaker alterne le sens des passes : une passe gauche-droite (les grands montent), une passe droite-gauche (les petits descendent — et un petit élément peut alors traverser tout le tableau en une passe). Sur l'exemple ci-dessus, deux passes suffisent. Le pire cas général reste $O(n^2)$, mais l'asymétrie pathologique disparaît. (Analyser un algorithme, c'est aussi comprendre la forme de ses mauvaises entrées — ici, l'asymétrie gauche-droite du mouvement — car c'est elle qui suggère le remède.)