Différence entre le tri des bulles et le tri de l'insertion

Toi à bulles vs tri insertion

Bubble Sort est un algorithme de tri qui fonctionne en parcourant la liste pour être triés à plusieurs reprises tout en comparant des paires d'éléments qui sont adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont échangés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun autre échange ne soit requis. Le tri d'insertion est également un algorithme de tri, qui fonctionne en insérant un élément dans la liste des entrées dans 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 des bulles?

Bubble Sort est un algorithme de tri qui fonctionne en parcourant la liste pour être triés à plusieurs reprises tout en comparant des paires d'éléments qui sont adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont échangés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun autre échange ne soit requis (ce qui signifie que la liste est triée). Étant donné que les petits éléments de la liste arrivent au sommet alors qu'une bulle revient à la surface, il reçoit le type de bulle de nom. Le tri à bulles est un algorithme de tri très simple, mais il a une complexité de temps de cas moyenne de O (n2) lors du tri d'une liste avec n éléments. Pour cette raison, le tri des bulles ne convient pas pour le tri des listes avec un grand nombre d'éléments. Mais à cause de sa simplicité, le tri de bulles est enseigné lors des introductions aux algorithmes.

Qu'est-ce que le tri de l'insertion?

Le tri d'insertion est un autre algorithme de tri, qui fonctionne en insérant un élément dans la liste des entrées dans la position correcte dans une liste (qui est déjà triée). Ce processus est appliqué à plusieurs reprises jusqu'à ce que la liste soit triée. En cas d'insertion, le tri est effectué en place. Par conséquent, après la ith itération de l'algorithme, les premières entrées I + 1 de la liste seront triées et le reste de la liste sera non. À chaque itération, le premier élément de la partie non triée de la liste sera prise et insérée au bon endroit dans la section triée de la liste. Le tri de l'insertion a une complexité de temps de cas moyenne de O (N2). Pour cette raison, le tri d'insertion ne convient pas non plus pour trier les grandes listes.

Quelle est la différence entre le tri des bulles et le tri d'insertion?

Même si les algorithmes de tri à bulles et de tri d'insertion ont des complexités de temps de cas moyen d'O (N2), le tri des bulles est presque tout le temps surperformé par le tri d'insertion. Cela est dû au nombre de swaps nécessaires aux deux algorithmes (les tri à bulles ont besoin de plus d'échanges). Mais en raison de la simplicité du tri des bulles, sa taille de code est très petite. Il existe également une variante du type d'insertion appelé le tri de la coquille, qui a une complexité temporelle d'O (N3 / 2), qui permettrait qu'il soit utilisé pratiquement. De plus, le tri d'insertion est très efficace pour trier les listes «presque triées», par rapport au tri des bulles.