#Algorithmes de triCopier le lien

Prérequis: tableaux, boucles, récursion, analyse de complexité (chapitre correspondant), tas binaire (module Structures de données).

Objectifs:

• Comprendre pourquoi aucun tri par comparaison ne descend sous Ω(n log n) dans le pire cas.
• Pour chaque tri dominant: l'invariant de correction, les coûts (pire, moyen, meilleur), les propriétés (stabilité, place).
• Savoir quand un tri non comparatif s'impose et à quelles conditions.

Le tri est le banc d'essai parfait: chaque algorithme porte un compromis différent entre simplicité, garanties et usage mémoire, et chacun se prouve par un invariant.

#La borne inférieure des tris par comparaisonCopier le lien

Théorème: tout algorithme de tri qui ne peut qu'ordonner deux éléments en les comparant effectue Ω(n log n) comparaisons dans le pire cas.

Preuve: pour une entrée de taille n, le comportement de l'algorithme (suite des comparaisons et échanges) est déterminé par l'ordre initial, inconnu. Représentons son exécution par un arbre de décision binaire (comparaison = nœud interne, deux branches selon le résultat). Il doit exister au moins une feuille distincte par permutation possible de l'entrée, donc au moins n! feuilles. Un arbre binaire de hauteur h a au plus 2^h feuilles: , d'où (l'encadrement de log(n!) est établi dans le chapitre Complexité des algorithmes). Le pire cas suit au moins un chemin racine-feuille de cette hauteur.

Conséquence: tri fusion et tri par tas atteignent la borne (Θ(n log n) garantie). Sortir de la borne exige de ne pas décider uniquement par comparaisons: c'est le rôle des tris non comparatifs en fin de chapitre.

#Ce que le modèle de l'arbre de décision suppose exactementCopier le lien

Un tri par comparaison n'obtient d'information sur l'ordre des éléments que par des tests du type A[i] ≤ A[j], A[i] < A[j], A[i] = A[j], etc. Il n'inspecte pas les valeurs autrement: aucun accès à la représentation binaire, aucun calcul arithmétique sur les clés. Trois précisions rendent la preuve rigoureuse.

• Éléments distincts sans perte de généralité. On prouve la borne pour des entrées à éléments deux à deux distincts. Un minorant obtenu sur ce sous-ensemble d'entrées reste un minorant sur l'ensemble complet, qui contient ces entrées.
• Les tests d'égalité sont inutiles. Un tri correct n'a jamais besoin de conclure A[i] = A[j]: il peut toujours traiter l'égalité comme A[i] ≤ A[j], ce qui donne un ordre valide. Les quatre tests ≤, ≥, <, > sont donc équivalents en information; on suppose que toutes les comparaisons ont la forme A[i] ≤ A[j].
• Chaque permutation doit être une feuille atteignable. Un arbre de décision est un arbre binaire complet (chaque nœud est une feuille ou a deux enfants). Chaque nœud interne est étiqueté par une comparaison i : j portant sur les positions initiales des éléments; chaque feuille est étiquetée par la permutation ⟨π(1), …, π(n)⟩ établie. La longueur du plus long chemin de la racine à une feuille atteignable est le nombre de comparaisons dans le pire cas; la borne sur la hauteur de l'arbre est donc une borne sur le coût de l'algorithme.

Corollaire. Tri fusion et tri par tas sont asymptotiquement optimaux parmi les tris par comparaison: leurs bornes supérieures Θ(n log n) coïncident avec la borne inférieure Ω(n log n) du théorème. Aucun tri par comparaison ne peut être plus rapide qu'eux de plus d'un facteur constant.

Exercice. Quel est le plus petit nombre de comparaisons possible dans le meilleur cas d'un tri par comparaison? Réponse: n − 1. Une feuille située à profondeur d correspond à une exécution qui n'a effectué que d comparaisons; ces comparaisons définissent un ordre partiel sur les n éléments, et la feuille n'est légitime que si cet ordre partiel admet une unique extension totale. Or un ordre partiel sur n éléments n'a une unique extension totale que si son graphe de comparabilité est connexe, ce qui demande au moins n − 1 arêtes. Donc toute feuille est à profondeur ≥ n − 1, et l'algorithme qui compare A[1] à A[2], puis A[2] à A[3], etc., atteint cette profondeur sur l'entrée déjà triée.

Exercice. On sait que l'entrée est partiellement triée: l'élément initialement en position i avec i mod 4 = 0 est à sa place définitive ou à une position d'écart; rien n'est connu des autres positions. La borne Ω(n log n) tient-elle encore? Oui. Restreignons-nous au sous-ensemble des entrées où les éléments contraints sont déjà à leur place: les 3n/4 éléments restants peuvent alors occuper les positions libres dans n'importe quel ordre, ce qui donne (3n/4)! entrées distinctes, donc au moins (3n/4)! feuilles atteignables, donc une hauteur d'arbre au moins log((3n/4)!) = Θ(n log n). Une entrée partiellement triée ne fait pas tomber la borne du pire cas; elle abaisse seulement le coût de certains algorithmes adaptatifs sur ces entrées.

#Tris quadratiquesCopier le lien

#Tri par insertionCopier le lien

Invariant: au début de l'itération i, le segment t[0..i−1] contient les i premiers éléments de l'entrée, triés. L'itération prend t[i], décale vers la droite les éléments plus grands, et l'insère à sa place.

Suivez la trace sur [5, 3, 1, 4] dans la visualisation: la zone triée grandit d'une case à chaque itération, le trait marquant la frontière.

Le pseudocode du cours, en indices 1 à n:

1INSERTION-SORT(A, n)21  pour i = 2 à n32      clé = A[i]                      // l'élément à insérer dans la main43      // insérer A[i] dans la zone triée A[1..i−1]54      j = i − 165      tant que j > 0 et A[j] > clé76          A[j+1] = A[j]                // décaler vers la droite87          j = j − 198      A[j+1] = clé

Invariant de boucle, énoncé exact: au début de chaque itération de la boucle pour (indice i), le sous-tableau A[1..i−1] contient les éléments initialement en A[1..i−1], mais en ordre trié.

• Initialisation. Avant la première itération, i = 2 et A[1..1] se réduit à A[1], qui est bien l'élément initialement en position 1 et qui est trié par trivialité.
• Maintenance. La boucle tant que déplace vers la droite tous les éléments strictement supérieurs à clé, puis écrit clé dans la première case libre rencontrée. Avant l'itération, A[1..i−1] est trié et contient les éléments initiaux de A[1..i−1]; après, A[1..i] est trié et contient les éléments initiaux de A[1..i]. Incrémenter i rétablit donc l'invariant.
• Terminaison. La boucle s'arrête quand i dépasse n, c'est-à-dire quand i = n + 1. En substituant cette valeur dans l'invariant: A[1..n] contient les éléments initialement en A[1..n], en ordre trié. L'algorithme est correct.

C'est une récurrence déguisée: la maintenance est l'étape inductive, l'initialisation le cas de base, et la terminaison arrête l'induction pour conclure sur l'état final.

#Le coût exact, ligne par ligneCopier le lien

Chaque ligne coûte un temps constant c_k par exécution; les lignes 5 à 7 s'exécutent t_i fois pour l'itération i (le nombre de décalages plus un).

Le coût total est donc

T(n) = c₁n + (c₂ + c₄ + c₈)(n − 1) + c₅ Σᵢ tᵢ + (c₆ + c₇) Σᵢ (tᵢ − 1)

où les sommes portent sur i = 2..n. Tout le comportement de l'algorithme est encapsulé dans les tᵢ: c'est le contenu de l'entrée, et rien d'autre, qui décide du coût.

Meilleur cas (entrée déjà triée). La condition A[j] > clé est fausse dès le premier test, donc tᵢ = 1 pour tout i. Les sommes valent Σ tᵢ = n − 1 et Σ (tᵢ − 1) = 0:

T(n) = c₁n + (c₂ + c₄ + c₅ + c₈)(n − 1) = an + b = Θ(n)

Une comparaison par élément, aucun décalage: le coût est linéaire, et l'algorithme détecte le tri en le lisant une fois.

Pire cas (entrée triée à l'envers). L'élément A[i] est plus petit que tous ceux qui le précèdent, donc le tant que va jusqu'au bout: tᵢ = i. Alors Σᵢ₌₂ⁿ tᵢ = n(n+1)/2 − 1 et Σᵢ₌₂ⁿ (tᵢ − 1) = n(n−1)/2:

T(n) = (c₅/2 + c₆/2 + c₇/2)n² + (c₁ + c₂ + c₄ + c₅/2 − c₆/2 − c₇/2 + c₈)n − (c₂ + c₄ + c₈) = an² + bn + c = Θ(n²)

Le n² vient de la somme arithmétique des décalages: 1 + 2 + … + (n−1) = n(n−1)/2. Aucune astuce d'implémentation ne fait disparaître ce terme dans le modèle de comparaison; il faudra une autre stratégie (diviser pour régner) pour y échapper.

Cas moyen. Si toutes les permutations de l'entrée sont équiprobables, l'élément A[i] doit être inséré en moyenne au milieu de la zone triée, soit i/2 décalages: Σᵢ i/2 = n(n−1)/4 = Θ(n²). Même classe que le pire cas, constante deux fois plus petite.

#Trace complète du tri par insertionCopier le lien

Sur A = ⟨5, 2, 4, 6, 1, 3⟩, en indiquant après chaque itération le contenu du tableau et la zone triée (entre crochets):

Détail de l'itération i = 5, la plus instructive: le tableau est 2 4 5 6 1 3, clé = 1. La boucle tant que décale 6, puis 5, puis 4, puis 2 (quatre décalages, j descend jusqu'à 0), puis écrit 1 en position 1. Le nombre total de décalages sur cette entrée vaut 1 + 1 + 0 + 4 + 3 = 9, à comparer aux n(n−1)/2 = 15 du pire cas et aux n − 1 = 5 du meilleur cas.

Coûts: pire cas Θ(n²) (entrée triée à l'envers, chaque élément traverse toute la zone triée); meilleur cas Θ(n) (entrée déjà triée: une comparaison par élément, aucun décalage); moyen Θ(n²). Stable (les éléments égaux conservent leur ordre relatif, car on ne décale que les strictement plus grands: la condition A[j] > clé est stricte) et en place, O(1) d'espace auxiliaire.

Usage: petits tableaux (des constantes minuscules battent le n log n), tableaux presque triés (coût quasi linéaire, d'où son rôle de finition dans les tris hybrides: Timsort utilisé par Python, segments courts dans les implémentations réelles du tri rapide).

#Pourquoi l'insertion gagne sur les petits tableaux: le seuil exactCopier le lien

Considérons un tri fusion modifié qui trie d'abord n/k sous-listes de longueur k par tri par insertion, puis fusionne ces n/k listes par le mécanisme standard.

1. Le tri par insertion des n/k sous-listes coûte Θ(k²) chacune, soit Θ(nk) au total.
2. La fusion des n/k listes triées demande lg(n/k) niveaux de fusion, chacun en Θ(n): Θ(n lg(n/k)).
3. Total: Θ(nk + n lg(n/k)).

Comparé à Θ(n lg n) pour le tri fusion pur, le terme supplémentaire nk est négligeable exactement quand k = Θ(lg n). En dessous de cette taille, la version hybride reste asymptotiquement identique au tri fusion et gagne les constantes; au-dessus, elle dégénère. En pratique on ne choisit pas k théoriquement mais expérimentalement, sur la machine et le langage réels: c'est le plus grand k pour lequel le tri par insertion reste plus rapide que le tri fusion sur une liste de k éléments. C'est exactement ce que font Timsort (seuil de 32 à 64 selon les implémentations) et les tris rapides de bibliothèque standard.

#Tri par sélectionCopier le lien

Invariant: après l'itération i, t[0..i−1] contient les i plus petits éléments de l'entrée, triés et à leur place définitive. L'itération cherche le minimum de t[i..n−1] et l'échange avec t[i].

Inspection visuelle sur la même entrée:

Coût: exactement n(n−1)/2 comparaisons dans tous les cas (on scanne toujours tout le reste du tableau): Θ(n²), aucun meilleur cas. Mais au plus n − 1 échanges: c'est le tri à retenir quand l'écriture est très coûteuse (grosses structures, mémoire flash). Non stable dans sa version classique (l'échange déplace un élément par-dessus d'autres).

#Tri à bullesCopier le lien

Compare chaque paire adjacente et échange si nécessaire, en propageant le plus grand vers la fin; on répète jusqu'à ce qu'une passe complète ne fasse aucun échange.

Coûts: Θ(n²) en moyenne et au pire, Θ(n) au mieux (détection d'arrêt sur entrée triée). Stable et en place, mais plus d'échanges que le tri par insertion pour un même profil. Intérêt strictement pédagogique: il matérialise la notion d'invariant (après la passe j, les j plus grands sont en place à la fin), mais aucune raison de l'employer.

#Tris en Θ(n log n)Copier le lien

#Tri fusion (merge sort)Copier le lien

Diviser pour régner, sur l'invariant suivant: la fusion de deux segments triés rend un segment trié.

1. Couper le tableau en deux moitiés.
2. Trier récursivement chaque moitié.
3. Fusionner: comparer les têtes des deux segments, extraire la plus petite, répéter.

1def tri_fusion(t):2    if len(t) <= 1:3        return t4    mi = len(t) // 25    gauche = tri_fusion(t[:mi])6    droit = tri_fusion(t[mi:])7    return fusion(gauche, droit)8 9def fusion(g, d):10    resultat = []11    i = j = 012    while i < len(g) and j < len(d):13        if g[i] <= d[j]:        # <= garantit la stabilité14            resultat.append(g[i]); i += 1

Le pseudocode du cours, avec la fusion sur place et ses sentinelles:

1MERGE-SORT(A, p, r)21  si p < r32      q = ⌊(p + r) / 2⌋                 // point de coupe43      MERGE-SORT(A, p, q)               // trier A[p..q]54      MERGE-SORT(A, q+1, r)             // trier A[q+1..r]65      MERGE(A, p, q, r)                 // fusionner les deux moitiés7 8MERGE(A, p, q, r)91  n₁ = q − p + 1 ;  n₂ = r − q102  soient L[1..n₁+1] et R[1..n₂+1] deux tableaux neufs113  pour i = 1 à n₁ :  L[i] = A[p + i − 1]      // copier la moitié gauche124  pour j = 1 à n₂ :  R[j] = A[q + j]          // copier la moitié droite135  L[n₁ + 1] = ∞ ;  R[n₂ + 1] = ∞              // sentinelles146  i = 1 ;  j = 1

Les deux sentinelles valant +∞ ne sont jamais recopiées dans A: dès qu'une des deux moitiés est épuisée, sa sentinelle perd tous les tests et c'est l'autre moitié qui se déverse. Elles suppriment les deux tests de bord (« i est-il encore dans L? ») du corps de boucle, au prix de deux cases supplémentaires.

#Invariant de la fusionCopier le lien

Invariant. Au début de chaque itération de la boucle pour k, le sous-tableau A[p..k−1] contient les k − p plus petits éléments de L[1..n₁+1] et R[1..n₂+1], en ordre trié. De plus, L[i] et R[j] sont les plus petits éléments de leurs tableaux respectifs qui n'ont pas encore été recopiés dans A.

• Initialisation. k = p, donc A[p..k−1] est vide et contient bien les 0 plus petits éléments. i = j = 1, donc L[1] et R[1] sont les plus petits éléments non recopiés de chaque tableau.
• Maintenance. Supposons L[i] ≤ R[j]. Alors L[i] est le plus petit élément non encore recopié de L ∪ R. Comme A[p..k−1] contient les k − p plus petits, écrire L[i] en A[k] fait que A[p..k] contient les k − p + 1 plus petits, en ordre trié (car L[i] ≥ A[k−1] par l'hypothèse). Incrémenter i rétablit la seconde partie de l'invariant. Le cas L[i] > R[j] est symétrique, avec R.
• Terminaison. À la sortie, k = r + 1: A[p..r] contient les r − p + 1 plus petits éléments de L ∪ R en ordre trié. Or L et R contiennent à eux deux exactement les éléments initialement dans A[p..r]. Donc A[p..r] est trié.

Coût de MERGE. Les lignes 1 à 6 prennent un temps constant; les deux copies prennent Θ(n₁ + n₂) = Θ(n) où n = r − p + 1. La boucle finale s'exécute exactement n fois, puisque chaque itération recopie un élément et que chaque élément est recopié une fois: au total Θ(n). Le coût de la fusion est donc linéaire en la taille du segment fusionné, quelle que soit la répartition des valeurs.

#Analyse du tri fusionCopier le lien

Récurrence. Les trois étapes de la méthode diviser pour régner donnent chacune leur terme.

• Diviser: calculer le milieu q coûte Θ(1).
• Régner: deux sous-problèmes de taille n/2, soit 2T(n/2).
• Combiner: une fusion sur n éléments, soit Θ(n).

T(n) = Θ(1) si n = 1, sinon T(n) = 2T(n/2) + Θ(n).

Théorème maître. Ici a = 2, b = 2, donc c = log₂ 2 = 1, et f(n) = Θ(n) = Θ(n^c): c'est le cas 2, d'où T(n) = Θ(n^c log n) = Θ(n log n).

Dérivation par arbre de récurrence. Pour n puissance de 2, notons cn le coût de découpe et de fusion au niveau supérieur:

• niveau 0: coût cn;
• niveau 1: 2 nœuds, chacun coûtant c(n/2), total 2 × cn/2 = cn;
• niveau j: 2^j nœuds, chacun coûtant c(n/2^j), total 2^j × cn/2^j = cn.

Chaque niveau coûte donc cn: doubler le nombre de nœuds divise exactement par deux le travail de chacun. Il y a lg n + 1 niveaux au total (du niveau 0 au niveau des feuilles), chaque niveau coûtant cn, soit un total de cn(lg n + 1) = cn lg n + cn = Θ(n log n). Le terme cn des feuilles correspond aux n sous-tableaux de taille 1, chacun résolu en temps constant.

Le point capital: aucun terme de cette somme ne dépend de l'ordre des valeurs. La structure des appels récursifs ne dépend que de n. C'est pourquoi le tri fusion est en Θ(n log n) dans tous les cas, meilleur, moyen et pire — contrairement au tri rapide.

Coûts: dans tous les cas (Master Theorem, cas 2): l'entrée n'a aucune influence sur la structure des appels. Espace: Θ(n) auxiliaire (segments temporaires). Stable (le <= de la fusion conserve l'ordre des égaux entre segments). Non en place au sens strict.

#Trace complète du tri fusionCopier le lien

Sur A = ⟨12, 3, 7, 9, 14, 6, 11, 2⟩, la descente coupe jusqu'aux singletons, puis la remontée fusionne:

Détail de la fusion 5, la première à comparer deux éléments de chaque côté: têtes 3 et 7 → 3 sort; têtes 12 et 7 → 7; 12 et 9 → 9; il ne reste que 12, déversé avec sa sentinelle. Détail de la fusion 7, la fusion finale: 3/2 → 2; 3/6 → 3; 7/6 → 6; 7/11 → 7; 9/11 → 9; 12/11 → 11; 12/14 → 12; reste 14. Vérifiez que l'ordre relatif des éléments égaux est préservé: c'est la seule chose que le choix de ≤ (et non <) dans la comparaison achète.

C'est le tri de la garantie: échéance stricte, données adverses, flux externes (tri externe sur disque: la fusion séquentielle s'adapte aux lectures séquentielles).

#Tri rapide (quick sort)Copier le lien

Invariant: après le partitionnement autour d'un pivot, le pivot est à sa place définitive, tout ce qui est plus petit à sa gauche, plus grand à sa droite.

1. Choisir un pivot.
2. Partitionner: répartir les éléments de part et d'autre.
3. Trier récursivement les deux côtés.

Coûts: meilleur et moyen (partitions équilibrées, ); pire cas Θ(n²) quand le pivot est systématiquement extrémal (entrée déjà triée avec pivot au premier élément: ). Espace: O(log n) en moyenne (pile de récursion), O(n) au pire cas.

Parades au pire cas: pivot aléatoire (l'espérance du coût reste Θ(n log n) quelle que soit l'entrée: le hasard est côté de l'algorithme, l'adversaire ne peut plus viser le pivot), médiane de trois éléments, coupure vers le tri par insertion sous un petit seuil. En place, généralement le plus rapide en pratique sur tableaux en mémoire (excellentes constantes: accès séquentiels, peu de copies), mais non stable dans les versions en place.

#Tri par tas (heap sort)Copier le lien

1. Construire un tas max en place dans le tableau: O(n) (voir le chapitre Arbres et tas).
2. Répéter: échanger la racine (maximum) avec le dernier élément, réduire la taille logique du tas, faire descendre la nouvelle racine: O(log n) par extraction.

Le tableau se remplit du plus grand au plus petit, depuis la fin. Coût Θ(n log n) garanti, O(1) espace auxiliaire, toutes les opérations sur place. Non stable. C'est le tri de la garantie en place: il ne devance jamais le tri rapide en moyenne, mais il ne peut ni dégénérer comme lui ni consommer comme le tri fusion.

#RécapitulatifCopier le lien

Lecture: aucune ligne ne domine sur toutes les colonnes. Fusion est le choix de robustesse, rapide le choix de vitesse moyenne sous pivot aléatoire, tas le choix de la garantie en place, insertion le choix des petites tailles et des entrées presque triées.

#Tris non comparatifsCopier le lien

Ces tris échappent à la borne Ω(n log n) en exploitant la valeur des éléments, pas uniquement leur ordre. La contrepartie: chacun impose des conditions sur les données.

#Tri par comptageCopier le lien

Pour des entiers dans un intervalle [0, k]:

1. Compter les occurrences de chaque valeur: O(n).
2. Reconstruire le tableau trié en déroulant les comptes, ou par comptes cumulés pour le rang de chaque élément: O(k).

Le pseudocode du cours:

1COUNTING-SORT(A, n, k)21  soit B[1..n] le tableau de sortie et C[0..k] un tableau de compteurs32  pour i = 0 à k43      C[i] = 0                            // aucun élément compté54  pour j = 1 à n65      C[A[j]] = C[A[j]] + 1               // C[i] = nombre d'éléments égaux à i76  // C[i] contient maintenant le nombre d'éléments égaux à i87  pour i = 1 à k98      C[i] = C[i] + C[i − 1]              // C[i] = nombre d'éléments ≤ i109  // C[i] contient maintenant le nombre d'éléments inférieurs ou égaux à i1110 pour j = n à 1                          // parcours ARRIÈRE: garantit la stabilité1211     B[C[A[j]]] = A[j]1312     C[A[j]] = C[A[j]] − 11413 renvoyer B

Trois remarques sur le pseudocode, chacune porteuse d'un piège:

• Les compteurs sont indexés de 0 à k, donc k + 1 cases: oublier la case d'indice 0 est l'erreur classique quand on transpose le pseudocode dans un langage à indices commençant à 0.
• La ligne 8 transforme les effectifs en rangs cumulés. Avant, C[i] dit combien d'éléments valent exactement i; après, C[i] dit combien valent au plus i, c'est-à-dire la position de sortie du dernier élément de valeur i.
• La ligne 10 parcourt l'entrée à l'envers, et c'est ce qui rend le tri stable. Voir la démonstration plus bas.

#CoûtCopier le lien

• Lignes 2 à 3: Θ(k).
• Lignes 4 à 5: Θ(n).
• Lignes 7 à 8: Θ(k).
• Lignes 10 à 12: Θ(n).

Total Θ(n + k), espace Θ(n + k) (les tableaux B et C). Quand k = O(n), le coût est Θ(n): c'est un tri linéaire. Le tri par comptage n'effectue aucune comparaison entre éléments d'entrée: il n'utilise que leur valeur comme indice. C'est précisément ce qui lui permet d'échapper au théorème de la borne Ω(n log n), qui ne vaut que pour les tris par comparaison.

En pratique, on emploie le tri par comptage quand k est du même ordre que n (trier les notes sur 100 d'un millier d'élèves: Θ(n + k) ≈ linéaire). Il devient absurde quand k explose: trier trois entiers de 64 bits par comptage demanderait 2⁶⁴ compteurs, soit plus de cases mémoire que d'atomes dans un grain de sable, pour trier trois nombres.

#Trace complète du tri par comptageCopier le lien

Sur A = ⟨2, 5, 3, 0, 2, 3, 0, 3⟩ (n = 8, k = 5):

Lecture des rangs cumulés: C[3] = 7 après la ligne 8 signifie « il y a 7 éléments inférieurs ou égaux à 3 ». Le dernier 3 de l'entrée doit donc aller en position 7. Les compteurs sont ensuite décrémentés, ce qui place chaque 3 suivant une case plus à gauche, en respectant l'ordre d'apparition initial.

#Invariant de la dernière boucleCopier le lien

Invariant. Au début de chaque itération de la boucle pour j, le dernier élément de A de valeur i qui n'a pas encore été recopié dans B doit être placé en B[C[i]].

• Initialisation. Avant la première itération (j = n), aucun élément n'a été recopié et C[i] vaut, pour chaque valeur i, le nombre d'éléments ≤ i, c'est-à-dire l'indice du dernier emplacement disponible pour la valeur i. L'élément A[n], de valeur v, doit donc aller en B[C[v]]: c'est exactement ce qu'écrit la ligne 11.
• Maintenance. Après avoir écrit A[j] en B[C[v]] et décrémenté C[v], les éléments de valeur v encore non recopiés sont exactement ceux d'indices < j, et C[v] pointe maintenant sur l'emplacement juste avant celui qu'on vient de remplir: l'invariant est conservé pour la valeur v. Pour les autres valeurs i ≠ v, ni les éléments concernés ni C[i] n'ont changé.
• Terminaison. À j = 0, tous les éléments ont été recopiés; l'invariant garantit qu'ils l'ont été dans l'ordre croissant des valeurs, et donc B est trié.

#Stabilité, démontréeCopier le lien

Le tri par comptage est stable: deux éléments de même valeur apparaissent dans B dans le même ordre relatif que dans A.

Preuve: considérons deux éléments x et y de valeur v, avec x apparaissant avant y dans A (positions j_x < j_y). Le parcours se fait de j = n vers 1, donc y est traité avant x. À ce moment, C[v] vaut le nombre d'éléments ≤ v, c'est-à-dire la position de sortie du dernier élément de valeur v. y est donc écrit le plus à droite de la plage réservée aux v, puis C[v] est décrémenté. Quand x est traité à son tour, C[v] a diminué exactement du nombre d'éléments de valeur v traités entre-temps, dont y: x est donc écrit immédiatement à gauche de y. L'ordre initial est préservé.

Conséquence: remplacer le parcours arrière par un parcours avant (pour j = 1 à n) laisse l'algorithme correct — les mêmes éléments sont écrits aux mêmes positions, dans un ordre différent — mais détruit la stabilité: le premier élément de valeur v rencontré irait le plus à droite. C'est un cas rare d'algorithme à la fois correct et non stable selon l'ordre de parcours d'une boucle.

La stabilité n'est pas un luxe ici: c'est elle qui rend le tri par base correct (section suivante), puisque chaque passe doit préserver le classement établi par la précédente.

#Variantes utilesCopier le lien

• Tri en place avec deux tableaux. Si le tableau ne porte aucune donnée satellite (on ne trie que des clés), on peut se passer de B et recopier le résultat dans A, en utilisant C comme compteur d'écriture. L'algorithme reste linéaire mais n'est plus stable: l'information d'ordre d'apparition est perdue.
• Compter sur une plage. Pour répondre à « combien d'entiers de l'entrée tombent dans l'intervalle [a, b]? », il suffit des rangs cumulés: la réponse est C[b] − C[a − 1]. Après un prétraitement en Θ(n + k), chaque requête coûte Θ(1), ce qui est le bon compromis quand les requêtes sont nombreuses et l'entrée figée.
• Clés à partie fractionnaire. Si chaque clé a au plus d chiffres décimaux après la virgule, on multiplie tout par 10^d et on compte sur les entiers obtenus: Θ(n + 10^d).

#Tri par base (radix sort)Copier le lien

Trier les éléments par chiffre successif, du chiffre le moins significatif vers le plus significatif, avec un tri stable (comptage) à chaque passe. La stabilité est l'argument clé: le classement établi par une passe n'est pas détruit par la suivante, car les chiffres plus significatifs prennent le relais uniquement quand ils diffèrent.

1RADIX-SORT(A, n, d)21  pour i = 1 à d32      utiliser un tri stable pour trier A sur le chiffre i

Le pseudocode tient en deux lignes parce que toute la difficulté est dans le choix du tri stable. En pratique on emploie COUNTING-SORT, dont l'alphabet est la base choisie.

Lemme. Étant donné n nombres à d chiffres, chaque chiffre prenant au plus k valeurs possibles, RADIX-SORT trie correctement ces nombres en Θ(d(n + k)) si le tri stable utilisé coûte Θ(n + k).

Preuve de correction. Par récurrence sur la passe i. Après la passe i, les nombres sont triés selon leurs i chiffres de poids faible. Cas de base (i = 0): aucun chiffre traité, la propriété est vide. Étape: supposons les nombres triés sur les i − 1 chiffres de poids faible avant la passe i; le tri stable sur le chiffre i place les nombres par ordre du chiffre i, et, à chiffre i égal, conserve l'ordre établi par la passe précédente (c'est exactement la stabilité). Or deux nombres qui ont le même chiffre i se comparent par leurs chiffres de poids faible: l'ordre hérité est donc le bon. Ceux qui diffèrent sur le chiffre i sont ordonnés par lui, ce qui est correct puisque c'est le chiffre le plus significatif parmi les i traités. Après d passes, les nombres sont triés sur les d chiffres, c'est-à-dire complètement.

Preuve du coût. Chaque passe est un tri par comptage sur n éléments et un alphabet de k valeurs: Θ(n + k). Il y a d passes, d'où Θ(d(n + k)). Quand d est constant et k = O(n), le coût total est Θ(n): radix sort est linéaire.

Trace. Sur les sept nombres à trois chiffres décimaux 329, 457, 657, 839, 436, 720, 355:

Détail de la passe 1 (unités): 720 (0), 355 (5), 436 (6), 457 (7), 657 (7), 329 (9), 839 (9). Les deux nombres d'unité 7 sortent dans leur ordre d'entrée (457 avant 657) et les deux d'unité 9 également (329 avant 839): c'est la stabilité à l'œuvre. Passe 2 (dizaines) sur cette liste: 720 et 329 ont 2, 436 et 839 ont 3, 355, 457 et 657 ont 5 — les groupes sortent dans l'ordre 2, 3, 5 et, à l'intérieur de chaque groupe, dans l'ordre hérité de la passe 1, ce qui met 329 après 720 (dizaine 2) puis 436 avant 839 (dizaine 3). Passe 3 (centaines): 329 et 355 (3), 436 et 457 (4), 657 (6), 720 (7), 839 (8). Le résultat final est trié.

Généralisation aux clés binaires. Pour des nombres de b bits et un entier r ≤ b, on découpe chaque clé en ⌈b/r⌉ chiffres de r bits, chacun valant entre 0 et 2^r − 1. Chaque passe coûte alors Θ(n + 2^r) et le total vaut Θ((b/r)(n + 2^r)). Si b = O(lg n), le meilleur choix est r = b, une seule passe en Θ(n). Si b > lg n, le r optimal vaut lg n, ce qui donne Θ(bn / lg n). Sur des entiers 32 bits on peut par exemple prendre r = 8 (quatre passes sur des chiffres d'un octet), choix courant parce qu'il rend le tableau de comptage minuscule et tient dans le cache.

Radix sort contre tri rapide. Si b = O(lg n) et r = lg n, radix sort est en Θ(n), apparemment meilleur que le Θ(n log n) attendu du tri rapide. Les constantes cachées renversent souvent la conclusion: chaque passe de radix sort balaie les clés en entier, alors qu'une comparaison de tri rapide ne touche qu'un mot. Sur une machine réelle, le tri rapide exploite mieux le cache et gagne fréquemment sur des clés de 32 ou 64 bits; radix sort reprend l'avantage sur des clés longues et de structure régulière (chaînes, IP, horodatages), et il n'est pas en place.

Pour d chiffres en base k: coût O(d(n + k)). Pour des entiers machine sur 64 bits en base 2¹⁶: d = 4 passes, O(n) en pratique. Conditions: clé décomposable en chiffres, alphabet fini.

#Tri par paniers (bucket sort)Copier le lien

Distribuer les éléments dans p paniers selon des bornes régulières, trier chaque panier (souvent par insertion), concaténer. Sous hypothèse d'une distribution à peu près uniforme dans l'intervalle des bornes, l'effectif moyen par panier est n/p: coût moyen O(n) avec p bien choisi. Le pire cas reste O(n²) (tous les éléments dans un panier). Sensible à la distribution: à réserver aux données qui la justifient.

#Exercice 1: le tri fusion est stableCopier le lien

Prouvez que le tri fusion tel qu'implémenté ci-dessus est stable.

Correction: la stabilité se joue uniquement dans la fusion. Quand les deux têtes sont égales, g[i] <= d[j] retient g[i], l'élément de gauche. Or, tout élément du segment gauche précède tout élément du segment droit dans l'ordre initial (la coupe est en deux moitiés contiguës, et les récursions trient sans réordonner entre segments). Donc pour deux éléments égaux, celui apparu en premier dans l'entrée est extrait le premier à chaque fusion, et par récursion sur les niveaux de fusion, l'ordre relatif initial est préservé jusqu'au résultat final. (Avec un < strict au lieu du <=, l'élément de droite sortirait le premier: la stabilité serait perdue, sans rien changer au coût.)

#Exercice 2: compter pour distinguer correct et rapideCopier le lien

Instrumentez le tri par sélection et le tri par fusion avec un compteur de comparaisons, et mesurez sur trois entrées de taille 2000: (a) triée, (b) triée à l'envers, (c) aléatoire.

Correction attendue (à confronter à vos mesures):

Le tri par sélection est un vrai tri (les trois sorties sont correctes, vérifiables avec sorted), mais insensible au contenu: exactement n(n−1)/2 comparaisons partout, 1 999 000 pour n = 2000. Le tri fusion: environ n log₂ n comparaisons, du même ordre sur les trois entrées, conformément au Θ(n log n) garanti. Ce que l'exercice enseigne: les deux tris sont corrects sur toute entrée, leurs courbes de flux de travail diffèrent radicalement; la correction se vérifie sur les sorties (les trois cases « trié: True »), la performance se vérifie sur les comptes, et aucune des deux preuves ne remplace l'autre.

#Exercice 3: dérouler le tri par insertionCopier le lien

Illustrez l'exécution de INSERTION-SORT sur A = ⟨31, 41, 59, 26, 41, 58⟩. Donnez l'état du tableau après chaque itération de la boucle pour et le nombre total de décalages.

Correction:

Total: 5 décalages, à comparer aux 15 du pire cas (n = 6, n(n−1)/2) et aux 5 du meilleur cas. Point à ne pas manquer à l'itération i = 5: la comparaison est A[j] > clé (strictement), donc le 41 déjà en place ne se décale pas et le nouveau 41 s'insère à sa droite. C'est exactement cette stricte inégalité qui rend le tri stable.

#Exercice 4: dérouler le tri fusionCopier le lien

Illustrez l'exécution de MERGE-SORT sur A = ⟨3, 41, 52, 26, 38, 57, 9, 49⟩: donnez la séquence des divisions et des fusions.

Correction:

Détail de la fusion finale, élément par élément: têtes 3 et 9 → 3; 26 et 9 → 9; 26 et 38 → 26; 41 et 38 → 38; 41 et 49 → 41; 52 et 49 → 49; 52 et 57 → 52; il ne reste que 57, déversé. Huit éléments triés en 7 comparaisons. Ce nombre n'est pas un minimum absolu: fusionner deux suites triées de 4 éléments demande au moins 4 comparaisons (cas où toute une moitié précède l'autre) et au plus 7 (les deux suites s'entrelacent complètement, comme ici). Le nombre total de comparaisons de l'algorithme est quant à lui toujours compris entre environ (n/2)·lg n et n·lg n − n + 1, quel que soit l'ordre de l'entrée.

#Exercice 5: dérouler le tri par comptageCopier le lien

Illustrez COUNTING-SORT sur A = ⟨6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2⟩ avec k = 6. Donnez C après chaque boucle, puis B.

Correction (n = 11, k = 6):

Vérification de la stabilité sur cet exemple: les deux 6 de A occupent les positions 1 et 8; ils sortent en positions 10 et 11, dans cet ordre. Les deux 3 occupent les positions 6 et 10; ils sortent en 7 et 8, dans cet ordre. Un parcours avant au lieu du parcours arrière aurait inversé chacun de ces couples.

#Exercice 6: le tri par insertion, version récursiveCopier le lien

Écrivez une version récursive du tri par insertion: pour trier A[1..n], on trie récursivement A[1..n−1], puis on insère A[n] à sa place dans la zone triée. Donnez la récurrence du coût dans le pire cas et sa solution.

Correction:

1INSERTION-SORT-REC(A, n)21  si n > 132      INSERTION-SORT-REC(A, n − 1)      // A[1..n−1] est maintenant trié43      clé = A[n]54      j = n − 165      tant que j > 0 et A[j] > clé76          A[j+1] = A[j]87          j = j − 198      A[j+1] = clé

La correction découle directement de l'invariant: après la ligne 2, A[1..n−1] est trié et contient les éléments initiaux de A[1..n−1]; les lignes 3 à 8 insèrent A[n] dans cette zone triée, comme dans la version itérative. Récurrence du pire cas: T(n) = T(n−1) + Θ(n), car l'insertion peut décaler jusqu'à n − 1 éléments. En déroulant, T(n) = Θ(n) + Θ(n−1) + … + Θ(1) = Θ(n²). La récursion ne change rien au coût: elle ne fait que déplacer la boucle pour dans la pile d'appels, et elle consomme Θ(n) d'espace de pile au lieu de O(1). Leçon: transformer une boucle en récursion n'améliore pas la complexité, et coûte de la mémoire.

#Exercice 7: recherche binaire dans le tri par insertionCopier le lien

Écrivez la recherche binaire, montrez qu'elle coûte Θ(lg n), puis répondez: remplacer la recherche linéaire de la boucle tant que du tri par insertion par une recherche binaire améliore-t-il le tri au pire cas jusqu'à Θ(n log n)?

Correction. Recherche binaire:

1RECHERCHE-BINAIRE(A, p, r, x)21  si p > r alors renvoyer NIL32  q = ⌊(p + r) / 2⌋43  si A[q] == x alors renvoyer q54  si A[q] < x alors renvoyer RECHERCHE-BINAIRE(A, q+1, r, x)65  sinon renvoyer RECHERCHE-BINAIRE(A, p, q−1, x)

Chaque appel élimine la moitié du tableau: T(n) = T(n/2) + Θ(1), donc T(n) = Θ(lg n) par le théorème maître (cas 2). La recherche binaire est correcte parce que le tableau est trié, ce qui permet de savoir de quel côté de A[q] se trouve x.

Réponse à la question: non. La recherche binaire fait tomber le nombre de comparaisons à Θ(n lg n) — chaque insertion coûte lg i au lieu de i — mais elle ne touche pas au nombre de décalages, qui reste Θ(n²) dans le pire cas: après avoir trouvé la position en Θ(lg n), il faut quand même décaler jusqu'à i − 1 éléments pour libérer la case. Le coût total est donc Θ(n lg n) + Θ(n²) = Θ(n²), inchangé. Le tri par insertion paie les déplacements, pas les comparaisons; seule une structure qui rend le déplacement local bon marché (liste chaînée, arbre) attaquerait ce terme — et elle introduirait un coût de parcours équivalent. C'est le tri fusion, avec sa copie linéaire par niveau, qui franchit réellement la barre.

#Exercice 8: deux éléments de somme donnée en Θ(n log n)Copier le lien

Étant donné un ensemble S de n entiers et un entier x, décidez s'il existe deux éléments de S dont la somme vaut exactement x. Votre algorithme doit coûter Θ(n log n) dans le pire cas.

Correction:

1DEUX-SOMMES(S, x)21  T = MERGE-SORT(S)                       // Θ(n log n)32  pour chaque a de T                      // n itérations43      si RECHERCHE-BINAIRE(T, x − a) ≠ NIL54          renvoyer VRAI                   // Θ(lg n) par recherche65  renvoyer FAUX

Coût: Θ(n log n) pour le tri, puis n recherches binaires en Θ(lg n) chacune, soit Θ(n lg n). Total Θ(n log n). Correction: si a + b = x avec a, b ∈ S, alors en parcourant a on finit par tester x − a = b, présent dans T (trié, donc la recherche binaire le trouve); inversement, tout succès de la ligne 3 exhibe un couple valide. Attention au cas a = b: le couple (a, a) n'est valide que si a apparaît deux fois dans S; avec la version « ensemble » (sans doublon), il faut exclure l'élément lui-même, ce que la recherche binaire ne fait pas seule — détail à traiter explicitement.

#Exercice 9: corriger le tri à bullesCopier le lien

Le tri à bulles classique est

1BUBBLESORT(A, n)21  pour i = 1 à n − 132      pour j = n à i + 143          si A[j] < A[j − 1]54              échanger A[j] et A[j − 1]

Énoncez les deux invariants (boucle interne, boucle externe) et prouvez-les. Quelle est la complexité dans le pire cas? Que manque-t-il à cette version pour avoir un meilleur cas linéaire?

Correction. Ce qu'il faut prouver pour la correction: (i) l'inégalité A′[1] ≤ A′[2] ≤ … ≤ A′[n] sur la sortie, et (ii) que A′ est une permutation de A — c'est-à-dire que l'algorithme ne perd ni ne duplique aucun élément. L'échange mutuel de deux cases préserve le multiensemble, donc (ii) est immédiat; tout le travail est dans (i).

Invariant de la boucle interne (lignes 2–4): au début de chaque itération d'indice j, A[j] est le minimum de A[j..n].

• Initialisation: j = n, et A[n] est le minimum de A[n..n].
• Maintenance: par hypothèse A[j] = min(A[j..n]). Le corps compare A[j] et A[j−1] et les échange si A[j] < A[j−1]; après le corps, A[j−1] = min(A[j−1], A[j]) = min(A[j−1..n]). Décrémenter j place cette valeur en position j−1, ce qui rétablit l'invariant pour le nouvel indice.
• Terminaison: à j = i, on a A[i] = min(A[i..n]).

Invariant de la boucle externe (lignes 1–4): au début de chaque itération d'indice i, le sous-tableau A[1..i−1] est trié et contient les i − 1 plus petits éléments de A.

• Initialisation: i = 1, le sous-tableau A[1..0] est vide.
• Maintenance: par la terminaison de la boucle interne, A[i] = min(A[i..n]). Comme A[1..i−1] contient déjà les i − 1 plus petits éléments, tous ≤ A[i], le sous-tableau A[1..i] est trié et contient les i plus petits éléments.
• Terminaison: à i = n, A[1..n−1] est trié et contient les n − 1 plus petits éléments; le dernier est donc en place et A est trié.

Complexité. Les deux boucles sont imbriquées sans dépendre du contenu: exactement n(n−1)/2 comparaisons, soit Θ(n²) dans tous les cas. Ce qui manque: un drapeau d'échange. En sortant de la boucle externe dès qu'une passe complète n'a provoqué aucun échange, on obtient Θ(n) sur une entrée déjà triée. La version ci-dessus, telle quelle, reste quadratique même sur une entrée triée — c'est la variante avec détection d'arrêt qui a un meilleur cas linéaire. Même améliorée, elle effectue davantage d'échanges que le tri par insertion sur le même profil d'entrée: sa valeur est pédagogique, elle matérialise l'invariant, pas pratique.