Différence entre le tri à bulle et le tri à insertion

Tri à bulles vs Tri à insertion

Le tri à bulles est un algorithme de tri qui consiste à parcourir la liste pour trier de manière répétée 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'aucun échange supplémentaire ne soit nécessaire. Le tri par insertion est également un algorithme de tri qui consiste à insérer un élément de 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.

Quel est le type de bulle?

Le tri à bulles est un algorithme de tri qui consiste à parcourir la liste pour trier de manière répétée 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'aucun échange supplémentaire ne soit nécessaire (ce qui signifie que la liste est triée). Étant donné que les éléments les plus petits de la liste arrivent en haut à la surface, une bulle s’apparente à la surface. Le tri à bulles est un algorithme de tri très simple, mais il a une complexité de temps de cas moyen de O (n2) lors du tri d'une liste avec n éléments. De ce fait, le tri par bulle ne convient pas au tri des listes comportant un grand nombre d'éléments. Mais en raison de sa simplicité, le tri à bulles est enseigné lors de l'introduction d'algorithmes.

Qu'est-ce que le tri par insertion??

Le tri par insertion est un autre algorithme de tri qui consiste à insérer un élément de 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. Dans le tri par insertion, le tri est effectué sur place. Par conséquent, après la vingtiè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é. À 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é de temps de cas moyen de O (n2). De ce fait, le tri par insertion ne convient pas non plus pour le tri de grandes listes.

Quelle est la différence entre le tri à bulle et le tri à insertion?

Même si les algorithmes de tri à bulle et de tri à insertion ont tous deux une complexité de temps de cas moyen de O (n2), le tri à bulle est presque toujours plus performant que le tri par insertion. Cela est dû au nombre de swaps requis par les deux algorithmes (les types de bulles nécessitent davantage de swaps). Mais en raison de la simplicité du tri à bulle, la taille de son code est très petite. Il existe également une variante de type d'insertion appelée type d'enveloppe, qui a une complexité temporelle de 0 (n3 / 2), ce qui lui permettrait d'être utilisée de manière pratique. De plus, le tri par insertion est très efficace pour trier les listes «presque triées» par rapport au tri en bulle..