Table des matières:
Définition - Que signifie Bubble Sort?
Le tri à bulles est un algorithme de tri qui fonctionne en parcourant à plusieurs reprises les listes qui doivent être triées, en comparant chaque paire d'éléments adjacents et en les échangeant s'ils sont dans le mauvais ordre. Cette procédure de passage est répétée jusqu'à ce qu'aucun échange ne soit nécessaire, indiquant que la liste est triée. Le tri à bulles tire son nom du fait que des éléments plus petits se déplacent vers le haut de la liste.
Le tri à bulles est également appelé tri par enfoncement ou tri par comparaison.
Techopedia explique Bubble Sort
Le tri à bulles a le pire des cas et la complexité moyenne de O (n2), où n est le nombre d'articles triés. Contrairement aux autres algorithmes de tri, le tri à bulles détecte si la liste triée est intégrée efficacement à l'algorithme. Les performances de tri des bulles sur une liste déjà triée sont O (n).
La position des éléments dans le tri à bulles joue un rôle important dans la détermination des performances. Les gros éléments au début ne posent pas de problème car ils sont facilement échangeables. Les petits éléments vers la fin se déplacent lentement vers le début. En tant que tels, ces éléments sont appelés lapins et tortues.
L'algorithme de tri à bulles peut être optimisé en plaçant des éléments plus grands dans la position finale. Après chaque passage, tous les éléments après le dernier échange sont triés et n'ont pas besoin d'être vérifiés à nouveau, sautant ainsi le suivi des variables échangées.
