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 à 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 mouvement des éléments de rang supérieur. Un tri par insertion présente les avantages de la simplicité et de faibles frais généraux.
Definir Tech 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, ce qui donne une liste de sortie triée croissante. À chaque itération, l'algorithme de tri supprime un élément à la fois, trouve l'emplacement approprié dans le tableau trié et l'insère à cet endroit. L'itération se poursuit jusqu'à ce que la liste entière soit triée.
Le tri par insertion présente de nombreux avantages. Il est simple à mettre en œuvre et assez efficace pour de petits ensembles de données, surtout si elles sont substantiellement 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 par 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 le tri en tas ou les algorithmes de tri rapide.