Tri par bulle vs Tri par insertion
Le tri par bulles est un algorithme de tri qui fonctionne en parcourant la liste à trier à plusieurs reprises tout en comparant des paires d'éléments adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont permutés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucune autre permutation ne soit nécessaire. Le tri par insertion est également un algorithme de tri, qui fonctionne en insérant un élément dans la liste d'entrée à la position correcte dans une liste déjà triée. Ce processus est appliqué à plusieurs reprises jusqu'à ce que la liste soit triée.
Qu'est-ce que le tri à bulles ?
Le tri par bulles est un algorithme de tri qui fonctionne en parcourant la liste à trier à plusieurs reprises tout en comparant des paires d'éléments adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont permutés pour les placer dans le bon ordre. Ce parcours est répété jusqu'à ce qu'aucun échange supplémentaire ne soit nécessaire (ce qui signifie que la liste est triée). Étant donné que les plus petits éléments de la liste arrivent en haut lorsqu'une bulle apparaît à la surface, on lui donne le nom de tri par bulle. Le tri à bulles est un algorithme de tri très simple mais il a une complexité temporelle moyenne de O(n2) lors du tri d'une liste à n éléments. Pour cette raison, le tri à bulles n'est pas adapté au tri de listes contenant un grand nombre d'éléments. Mais en raison de sa simplicité, le tri à bulles est enseigné lors des introductions aux algorithmes.
Qu'est-ce que le tri par insertion ?
Le tri par insertion est un autre algorithme de tri, qui fonctionne en insérant un élément dans la liste d'entrée à la bonne position dans une liste (qui est déjà triée). Ce processus est appliqué à plusieurs reprises jusqu'à ce que la liste soit triée. Dans le tri par insertion, le tri est effectué sur place. Par conséquent, après la ième itération de l'algorithme, les i+1 premières entrées de la liste seront triées et le reste de la liste ne sera pas trié. A chaque itération, le premier élément de la partie non triée de la liste sera pris et inséré au bon endroit dans la section triée de la liste. Le tri par insertion a une complexité temporelle moyenne de O(n2). De ce fait, le tri par insertion ne convient pas non plus au tri de grandes listes.
Quelle est la différence entre le tri à bulles et le tri par insertion ?
Même si les algorithmes de tri à bulles et de tri par insertion ont des complexités temporelles moyennes de O(n2), le tri à bulles est presque toujours surpassé par le tri par insertion. Cela est dû au nombre d'échanges nécessaires aux deux algorithmes (les tris à bulles nécessitent plus d'échanges). Mais en raison de la simplicité du tri à bulles, la taille de son code est très petite. Il existe également une variante du tri par insertion appelée tri shell, qui a une complexité temporelle de O(n3/2), ce qui permettrait de l'utiliser pratiquement. De plus, le tri par insertion est très efficace pour trier des listes "presque triées", par rapport au tri à bulles.
