Tri par bulles

Le tri par bulles (en Anglais : bubble sort) est un classique parmi les algorithmes de tri. Il effectue $n$ itérations, $n$ étant le nombre d'éléments à trier. La première itération se fait sur l'ensemble des $n$ éléments à trier et le résultat est l'élément le plus grand des $n$. Cet élément est ensuite exclu de l'ensemble. Le processus recommence avec les $n-1$ é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 $O(n \texttt{log} n)$ typique est incapable de déterminer l'élément le plus grand avant $O(n \texttt{log} n)$ 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 à $\texttt{log} n$, l'algorithme de tri par bulles est plus rapide qu'un algorithme en $O(n \texttt{log} n)$.

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.