Ce sont trois algorithmes de tri par comparaison simples avec une complexité O(n²). Ils sont lents sur de grandes entrées mais faciles à comprendre et utiles pour enseigner les mécanismes du tri.
Ce sont trois algorithmes de tri par comparaison simples avec une complexité O(n²). Ils sont lents sur de grandes entrées mais faciles à comprendre et utiles pour enseigner les mécanismes du tri.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Tri | Meilleur | Pire | Stable | Sur place |
|---|---|---|---|---|
| Bulles | O(n) | O(n²) | Oui | Oui |
| Sélection | O(n²) | O(n²) | Non | Oui |
| Insertion | O(n) | O(n²) | Oui | Oui |
Le tri par insertion est véritablement rapide pour les tableaux petits ou presque triés et est utilisé dans les tris hybrides. Évitez tous les trois sur de grandes données non triées — utilisez plutôt des tris en O(n log n).
Ces tris construisent l'intuition pour les invariants, les échanges et la stabilité avant de passer à des algorithmes avancés.
Le tri par insertion en particulier apparaît dans les tris de production (comme Timsort) pour les minuscules sous-tableaux.
Comprendre pourquoi ils sont O(n²) rend la progression vers les tris O(n log n) significative.