Définition - Que signifie le tri à bulles?
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 les éléments plus petits bouillonnent vers le haut de la liste.
Le tri à bulles est également appelé tri par affaissement ou tri par comparaison.
Definir Tech explique le tri à bulles
Le tri à bulles a une complexité moyenne et dans le pire des cas de O (n2), où n est le nombre d'éléments triés. Contrairement aux autres algorithmes de tri, le tri à bulles détecte si la liste triée est efficacement intégrée à l'algorithme. Les performances de tri à 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 des 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, ignorant ainsi le suivi des variables permutées.