Table des matières:
Définition - Que signifie le tri par insertion?
Le tri par insertion est un algorithme de tri dans lequel les éléments sont transférés un par un vers la bonne position. En d'autres termes, un tri par insertion aide à construire la liste triée finale, un élément à la fois, avec le déplacement des éléments de rang supérieur. Un tri par insertion présente les avantages de simplicité et de faible surcharge.
Techopedia explique le tri par insertion
Dans un tri par insertion, le premier élément du tableau est considéré comme trié, même s'il s'agit d'un tableau non trié. Dans un tri par insertion, chaque élément du tableau est vérifié avec les éléments précédents, résultant en une liste de sortie triée croissante. À chaque itération, l'algorithme de tri supprime un élément à la fois et trouve l'emplacement approprié dans le tableau trié et l'insère là. L'itération continue jusqu'à ce que la liste entière soit triée.
Il existe de nombreux avantages associés à un tri par insertion. Il est simple à mettre en œuvre et est assez efficace pour de petits ensembles de données, surtout si elles sont sensiblement triées. Il a une faible surcharge et peut trier la liste à mesure qu'il reçoit des données. Un autre avantage associé au tri par insertion est le fait qu'il n'a besoin que d'une quantité constante d'espace mémoire pour toute l'opération. Il est plus efficace que d'autres algorithmes similaires tels que le tri à bulles ou le tri par sélection.
Cependant, un tri par insertion est moins efficace sur des ensembles de données plus volumineux et moins efficace que les algorithmes de tri en tas ou de tri rapide.
