backend / algorithmes-structures-donnees
Tris efficaces : fusion, rapide, Timsort
Explication
Ce que vous allez apprendre
- Expliquer le principe "diviser pour régner" derrière le tri fusion et le tri rapide
- Démontrer pourquoi le tri fusion garantit O(n log n) dans tous les cas, y compris le pire
- Identifier pourquoi le tri rapide peut dégénérer en O(n²) et comment un pivot aléatoire corrige ce risque
- Comparer tri fusion (stable, O(n) en espace) et tri rapide (en place, instable) pour choisir selon le contexte
- Expliquer pourquoi Python utilise Timsort et comment il exploite les séquences déjà triées ("runs")
Dans quel contexte ?
Une équipe backend doit trier chaque nuit un fichier de 5 millions de transactions bancaires par montant avant de générer un rapport. Avec un tri par insertion en O(n²), ce traitement prendrait des jours ; avec un tri fusion ou sorted() en Python (Timsort, O(n log n)), il se termine en quelques secondes. Le choix de l'algorithme de tri n'est donc pas un détail académique : c'est ce qui différencie un batch nocturne qui termine à temps d'un batch qui bloque toute la chaîne de traitement du lendemain.
D'abord, pourquoi les tris simples ne suffisent plus
La leçon précédente a montré que bulle, sélection et insertion plafonnent à O(n²) parce qu'ils comparent des éléments deux à deux sans jamais exploiter de structure globale. Pour aller plus vite, il faut une idée différente : diviser le problème en petits morceaux, les résoudre séparément, puis combiner intelligemment les résultats.
Étape 1 : l'observation qui débloque le tri fusion
Fusionner deux listes DÉJÀ triées en une seule liste triée est facile et rapide : il suffit de comparer leurs deux premiers éléments restants, de garder le plus petit, et de répéter. Cette opération simple ne coûte que O(n).
Étape 2 : construire le tri fusion à partir de cette observation
Le tri fusion divise récursivement le tableau en deux moitiés, jusqu'à obtenir des éléments seuls, trivialement triés. Ensuite, il remonte en fusionnant ces petites listes triées deux par deux, jusqu'à reconstituer le tableau complet, entièrement trié.
Pourquoi cela donne O(n log n)
Diviser le tableau en deux, encore en deux, etc., prend log2(n) niveaux. Chaque niveau coûte O(n) de fusion au total, ce qui donne bien O(n log n), garanti quel que soit l'ordre initial des données, même dans le pire des cas.
Étape 3 : une approche différente, le tri rapide
Le tri rapide choisit un élément pivot et réorganise le tableau autour de lui : tout ce qui est plus petit à gauche, tout ce qui est plus grand à droite. Le pivot se retrouve alors définitivement à sa position finale, sans jamais avoir besoin d'être redéplacé.
Il reste un problème avec cette méthode
En répétant cette opération récursivement sur chaque moitié, on obtient en moyenne O(n log n), aussi rapide que le tri fusion. Mais si le pivot choisi est systématiquement le plus petit ou le plus grand élément (par exemple sur un tableau déjà trié), les partitions deviennent très déséquilibrées et la complexité dégénère en O(n²).
Piège fréquent
Choisir systématiquement le premier ou le dernier élément comme pivot du tri rapide est risqué : sur un tableau déjà trié (ou déjà trié à l'envers), cela produit le pire cas O(n²) à chaque fois. Un pivot aléatoire, ou la médiane de trois éléments, élimine ce risque en pratique.
La solution : introduire du hasard
Choisir le pivot au hasard élimine ce risque : aucune donnée d'entrée particulière ne peut plus systématiquement provoquer ce pire cas.
| Critère | Tri fusion | Tri rapide |
|---|---|---|
| Complexité garantie | O(n log n) dans tous les cas | O(n log n) en moyenne, O(n²) au pire |
| Espace supplémentaire | O(n) | O(log n) (pile de récursion) |
| Stable | Oui | Non, en général |
| Tri en place | Non | Oui |
Pour aller plus loin : Timsort, l'algorithme réellement utilisé par Python
Les données du monde réel contiennent souvent des séquences déjà triées ("runs"). Timsort les détecte et les fusionne directement, ce qui lui permet d'atteindre O(n) sur des données quasi triées, bien mieux que le O(n log n) théorique d'un tri comparatif classique.
Astuce
sorted() et list.sort() en Python utilisent Timsort, qui détecte automatiquement les séquences déjà triées dans vos données pour les fusionner directement. Sur des données réelles partiellement ordonnées, c'est souvent bien plus rapide que le O(n log n) théorique d'un tri comparatif générique.
Vers la suite
Cette idée de structure organisée pour accélérer la recherche revient ailleurs sous une forme différente : la prochaine leçon montre comment les tables de hachage atteignent, elles, un accès quasi instantané en O(1).
Commandes & code
Tris efficaces : fusion, rapide, Timsort
# --- Tri fusion (merge sort) : O(n log n) garanti, stable, O(n) espace additionnel ---
def tri_fusion(tableau: list[int]) -> list[int]:
if len(tableau) <= 1:
return tableau
milieu = len(tableau) // 2
gauche = tri_fusion(tableau[:milieu])
droite = tri_fusion(tableau[milieu:])
return _fusionner(gauche, droite)
def _fusionner(a: list[int], b: list[int]) -> list[int]:
resultat = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # "<=" (pas "<") garantit la STABILITÉ du tri
resultat.append(a[i]); i += 1
else:
resultat.append(b[j]); j += 1
resultat.extend(a[i:])
resultat.extend(b[j:])
return resultat
# --- Tri rapide (quicksort) : O(n log n) en moyenne, O(n^2) au pire cas, en place ---
def tri_rapide(tableau: list[int]) -> list[int]:
tableau = tableau.copy()
_tri_rapide_en_place(tableau, 0, len(tableau) - 1)
return tableau
def _tri_rapide_en_place(tableau: list[int], bas: int, haut: int) -> None:
if bas < haut:
position_pivot = _partitionner(tableau, bas, haut)
_tri_rapide_en_place(tableau, bas, position_pivot - 1)
_tri_rapide_en_place(tableau, position_pivot + 1, haut)
def _partitionner(tableau: list[int], bas: int, haut: int) -> int:
# Partition de Lomuto : le dernier élément sert de pivot
pivot = tableau[haut]
i = bas - 1 # frontière entre "éléments <= pivot" et le reste
for j in range(bas, haut):
if tableau[j] <= pivot:
i += 1
tableau[i], tableau[j] = tableau[j], tableau[i]
tableau[i + 1], tableau[haut] = tableau[haut], tableau[i + 1]
return i + 1
# Choix du pivot aléatoire : évite le pire cas O(n^2) sur des données déjà triées/adversariales
import random
def _partitionner_aleatoire(tableau: list[int], bas: int, haut: int) -> int:
index_aleatoire = random.randint(bas, haut)
tableau[index_aleatoire], tableau[haut] = tableau[haut], tableau[index_aleatoire]
return _partitionner(tableau, bas, haut)
# --- Quickselect : trouver le k-ième plus petit élément en O(n) en moyenne (sans trier) ---
def k_ieme_plus_petit(tableau: list[int], k: int) -> int:
tableau = tableau.copy()
return _quickselect(tableau, 0, len(tableau) - 1, k - 1)
def _quickselect(tableau: list[int], bas: int, haut: int, k: int) -> int:
if bas == haut:
return tableau[bas]
position_pivot = _partitionner(tableau, bas, haut)
if k == position_pivot:
return tableau[k]
elif k < position_pivot:
return _quickselect(tableau, bas, position_pivot - 1, k)
else:
return _quickselect(tableau, position_pivot + 1, haut, k)
assert k_ieme_plus_petit([7, 2, 1, 6, 8, 5], 3) == 5 # 3e plus petit de [1,2,5,6,7,8]
# --- Timsort : l'algorithme utilisé par sorted()/list.sort() en Python ---
# Principe : détecte les "runs" (sous-séquences déjà triées) dans les données réelles,
# les trie avec un insertion sort pour les petits runs, puis les fusionne comme un merge sort.
# Complexité : O(n log n) au pire cas, O(n) au MEILLEUR cas (données déjà/quasi triées).
donnees = [5, 1, 4, 2, 8, 5, 9, 1, 3]
donnees_triees = sorted(donnees) # Timsort, stable, ne modifie pas l'original
donnees.sort() # Timsort en place
donnees.sort(key=lambda x: -x) # tri décroissant via une clé
personnes = [("Bob", 25), ("Alice", 30)]
personnes.sort(key=lambda p: p[1], reverse=True) # tri par clé personnaliséeRésumé
- Tri fusion : O(n log n) garanti dans tous les cas, stable, mais O(n) d'espace additionnel.
- Tri rapide : O(n log n) en moyenne, en place (O(log n) espace pour la pile de récursion), mais O(n^2) au pire cas sans pivot aléatoire.
- Quickselect réutilise la partition du tri rapide pour trouver le k-ième élément en O(n) moyen, sans trier tout le tableau.
- Timsort (utilisé par Python) exploite les runs déjà triés présents dans les données réelles : O(n) au meilleur cas, O(n log n) au pire.
Exercices pratiques
Mission : comprendre pourquoi le batch nocturne s'est mis à ramer
Objectif : Diagnostiquer une dégénérescence du tri rapide sur des données déjà triées, puis la corriger.
Contexte
Le batch nocturne qui trie 5 millions de transactions bancaires par montant utilisait un tri rapide maison, avec le dernier élément systématiquement choisi comme pivot (partition de Lomuto). Il tournait normalement en quelques secondes, mais depuis que le fichier d'entrée arrive déjà pré-trié par le système amont (une optimisation récente d'un autre service), le batch met désormais plusieurs heures et sature le serveur.
Tu dois diagnostiquer pourquoi, puis corriger le choix du pivot.