backend / algorithmes-structures-donnees
Tris simples : bulle, insertion, sélection
Explication
Ce que vous allez apprendre
- Expliquer en une phrase la logique de chacun des trois tris simples : bulle, sélection, insertion
- Justifier pourquoi les trois sont en O(n²) au pire cas malgré des stratégies différentes
- Identifier le cas particulier où le tri par insertion devient quasi-linéaire (données presque triées)
- Choisir le bon tri simple selon la contrainte dominante (nombre d'échanges, stabilité, données presque triées)
- Expliquer ce que signifie la "stabilité" d'un tri et pourquoi elle compte dans certains cas réels
Dans quel contexte ?
Un développeur doit trier une liste de 30 employés par nom dans une page d'administration interne peu utilisée : un tri à bulles ou par insertion, bien que O(n²), est largement suffisant et plus simple à lire qu'un tri fusion — sur 30 éléments, la différence de performance est imperceptible. Ce même développeur découvre ensuite qu'un tableau de bord affiche 10 000 commandes déjà presque triées par date, avec seulement quelques nouvelles commandes ajoutées en fin de liste : un tri par insertion y est étonnamment proche du O(n), car chaque nouvel élément ne se décale que de quelques positions.
D'abord, que veut dire "trier", concrètement ?
Trier un tableau, c'est réorganiser ses éléments pour qu'ils apparaissent du plus petit au plus grand. Avant d'utiliser des algorithmes rapides, il est utile de comprendre trois stratégies simples, même si elles sont rarement le bon choix en production.
Prérequis
Comprendre la notation Big O (leçon 1) est indispensable pour comparer ces algorithmes : ils sont tous O(n²) au pire cas, la différence se joue sur les constantes et sur des cas particuliers comme les données presque triées.
Étape 1 : le tri à bulles, l'idée la plus naïve
On compare deux éléments voisins ; s'ils sont dans le mauvais ordre, on les échange. En répétant ce balayage de gauche à droite plusieurs fois, le plus grand élément restant "remonte" vers la fin à chaque passage, comme une bulle qui remonte à la surface.
Le défaut de cette méthode
Il faut potentiellement refaire n passages complets sur n éléments : chaque passage coûte O(n), répété n fois, cela donne O(n²). C'est simple à comprendre mais lent dès que le tableau grandit.
Étape 2 : le tri par sélection, une autre idée naïve
Plutôt que d'échanger des voisins au hasard, on cherche activement le plus petit élément du reste du tableau, puis on le place directement à sa position finale d'un seul échange. On répète cette recherche sur ce qu'il reste à trier.
L'avantage discret de cette approche
Le tri par sélection fait beaucoup de comparaisons mais très peu d'échanges (un seul par étape), ce qui compte quand chaque écriture est coûteuse, par exemple sur une mémoire flash. Sa complexité reste cependant O(n²) dans tous les cas, sans exception.
Étape 3 : le tri par insertion, une idée plus naturelle
Imagine trier des cartes à la main : on prend chaque nouvelle carte et on l'insère directement à sa bonne place parmi celles déjà triées, en décalant les autres si besoin. C'est exactement ce que fait le tri par insertion sur un tableau.
Pourquoi cette troisième méthode se distingue des deux autres
Sur un tableau déjà presque trié, chaque nouvel élément n'a besoin d'être décalé que de très peu de positions : la complexité réelle approche alors O(n), bien mieux que O(n²). C'est pourquoi le tri par insertion reste utilisé aujourd'hui, souvent caché à l'intérieur de tris hybrides comme Timsort.
| Tri | Complexité pire cas | Échanges | Stable ? | Bon cas d'usage |
|---|---|---|---|---|
| Bulles | O(n²) | Nombreux | Oui | Surtout pédagogique |
| Sélection | O(n²) | O(n), peu nombreux | Non, sans précaution | Écriture coûteuse (mémoire flash) |
| Insertion | O(n²), proche de O(n) si presque trié | Nombreux mais légers | Oui | Petits tableaux, données quasi triées |
Astuce
"Stable" signifie que deux éléments égaux gardent leur ordre relatif d'origine après le tri. C'est important quand on trie une liste déjà triée par un premier critère (par exemple trier par nom une liste déjà triée par date) : un tri stable préserve ce tri précédent pour les valeurs égales.
Le piège à retenir
Ces trois algorithmes comparent ou déplacent des éléments un par un sans jamais exploiter de structure globale sur les données : c'est précisément cette absence de vue d'ensemble qui les limite à O(n²) au pire cas.
Vers la suite
Pour dépasser ce mur du O(n²), il faut changer complètement de stratégie et exploiter une structure plus intelligente : c'est exactement ce que font le tri fusion et le tri rapide, présentés dans la prochaine leçon.
Commandes & code
Tris simples : bulle, insertion, sélection
# --- Tri à bulles (bubble sort) : O(n^2), stable, simple à comprendre ---
def tri_bulles(tableau: list[int]) -> list[int]:
tableau = tableau.copy()
n = len(tableau)
for i in range(n):
echange = False
for j in range(n - i - 1): # les i derniers sont déjà triés après chaque passe
if tableau[j] > tableau[j + 1]:
tableau[j], tableau[j + 1] = tableau[j + 1], tableau[j]
echange = True
if not echange: # optimisation : si aucun échange, le tableau est déjà trié
break
return tableau
# --- Tri par sélection (selection sort) : O(n^2), non stable, minimal en écritures ---
def tri_selection(tableau: list[int]) -> list[int]:
tableau = tableau.copy()
n = len(tableau)
for i in range(n):
index_min = i
for j in range(i + 1, n):
if tableau[j] < tableau[index_min]:
index_min = j
tableau[i], tableau[index_min] = tableau[index_min], tableau[i] # 1 seul échange par passe
return tableau
# --- Tri par insertion (insertion sort) : O(n^2) pire cas, O(n) si presque trié, stable ---
def tri_insertion(tableau: list[int]) -> list[int]:
tableau = tableau.copy()
for i in range(1, len(tableau)):
cle = tableau[i]
j = i - 1
while j >= 0 and tableau[j] > cle:
tableau[j + 1] = tableau[j] # décale vers la droite
j -= 1
tableau[j + 1] = cle
return tableau
# Tri par insertion : très efficace pour insérer un nouvel élément dans une liste DÉJÀ triée
def inserer_dans_liste_triee(tableau_trie: list[int], nouvelle_valeur: int) -> list[int]:
import bisect
position = bisect.bisect_left(tableau_trie, nouvelle_valeur) # O(log n) pour trouver la position
tableau_trie.insert(position, nouvelle_valeur) # O(n) pour le décalage physique
return tableau_trie
# Comparaison pratique : stabilité d'un tri (préserve l'ordre relatif des éléments égaux)
def tri_stable_demo():
personnes = [("Alice", 30), ("Bob", 25), ("Claire", 30), ("David", 25)]
# Un tri STABLE trié par âge préserve l'ordre initial entre personnes de même âge
trie_stable = sorted(personnes, key=lambda p: p[1])
# -> [("Bob", 25), ("David", 25), ("Alice", 30), ("Claire", 30)]
return trie_stable
# Vérifier qu'un tableau est trié : utile pour valider le résultat d'un algorithme
def est_trie(tableau: list[int]) -> bool:
return all(tableau[i] <= tableau[i + 1] for i in range(len(tableau) - 1))
for algo in (tri_bulles, tri_selection, tri_insertion):
assert est_trie(algo([5, 2, 8, 1, 9, 3]))| Algorithme | Meilleur cas | Pire cas | Espace | Stable |
|---|---|---|---|---|
| Bulles | O(n) | O(n^2) | O(1) | Oui |
| Sélection | O(n^2) | O(n^2) | O(1) | Non |
| Insertion | O(n) | O(n^2) | O(1) | Oui |
Résumé
- Ces trois tris sont en O(n^2) au pire cas : adaptés aux petits tableaux ou aux données presque triées.
- Le tri par insertion est le plus utile en pratique parmi les trois (adaptatif, performant sur données quasi triées).
- La stabilité (préserver l'ordre des éléments égaux) est cruciale quand on trie par une clé secondaire après une autre.
bisect.insortcombine recherche binaire + insertion pour insérer efficacement dans une liste déjà triée.
Exercices pratiques
Mission : choisir le bon tri pour un tableau de bord de commandes
Objectif : Choisir et justifier un algorithme de tri simple adapté à des données presque triées, puis raisonner sur la stabilité.
Contexte
Un tableau de bord interne affiche 10 000 commandes déjà triées par date. Toutes les quelques secondes, une poignée de nouvelles commandes arrive et doit être intégrée à la liste sans tout retrier depuis zéro. L'équipe hésite entre tri à bulles, tri par sélection et tri par insertion pour ce cas précis.
Tu dois justifier le bon choix, puis vérifier qu'il préserve un tri secondaire déjà en place (par nom de client, pour les commandes de même date).