Tri par insertion

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, adaptive sort (en), algorithme en place, algorithme en ligne
Structures des données	Tableau, insert (d)
À l'origine de	Timsort

Complexité en temps

Pire cas	${\displaystyle O(n^{2})}$
Moyenne	${\displaystyle O(n^{2})}$
Meilleur cas	${\displaystyle O(n)}$

Complexité en espace

Pire cas	${\displaystyle O(1)}$

modifier - modifier le code - modifier Wikidata

En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer^[1].

C'est un tri par file de priorité en utilisant l'implémentation par tableau trié des files de priorité^[2].

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.

Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille. Il est aussi efficace lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide.

En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin.