Le tri par bulles (en Anglais : bubble sort) est un classique parmi les
algorithmes de tri. Il effectue itérations,
étant le nombre
d'éléments à trier.
La première itération se fait sur l'ensemble des
éléments
à trier et le résultat est l'élément le plus grand des
. Cet
élément est ensuite exclu de l'ensemble. Le processus
recommence avec les
éléments restants et ainsi de suite
jusqu'au dernier. Il est également possible
de chercher le plus petit élément dans chaque itération.
L'avantage de cet algorithme est qu'il trouve immédiatement l'élément
le plus grand (ou plus petit selon le cas) en temps linéaire, alors
qu'un algorithme
typique est incapable de
déterminer l'élément le plus grand avant
itérations.
Ce type d'algorithme peut être utilisé dans une application
interactive, où les éléments d'un ensemble doivent être affichés dans
l'ordre et où l'utilisateur peut interrompre l'affichage quand il a
vu un nombre suffisant d'éléments. Si l'utilisateur interrompt
le calcul au bout d'un nombre d'éléments inférieur à
,
l'algorithme de tri par bulles est plus rapide
qu'un algorithme en
.
Dans la littérature, l'algorithme de tri par bulles est souvent présenté pour le tri de vecteurs, mais il est également possible de l'utiliser pour trier des listes.