Tri à bulles

Description

L'algorithme de tri à bulles marche à la fois sur les tableaux et sur les listes. Il fait n-1 itérations (où n est le nombre d'éléments de la séquence). La première itération parcourt l'ensemble des éléments, la deuxième itération parcourt les n-1 premiers éléments, etc. À chaque itération (sur les k premiers éléments), l'élément maximal parmi les k est trouvé, et à l'issu de l'itération cet élément est le dernier parmi les k éléments parcourus.

À chaque itération, l'algorithme parcourt les k éléments de la manière suivante : D'abord le premier et le deuxième éléments sont comparés. Si le premier est plus grand que le deuxième, alors on échange les deux. Le deuxième élément sera donc le plus grand des deux premier. Puis on compare le deuxième et le troisième élément et on échange si le deuxième est plus grand que le troisième. De cette façon, le plus grand élément sera poussé jusqu'à la dernière place parmi les k

Imlémentations

Stabilité

Le tri à bulles est stable. Deux éléments sont échangés seulement si le premier est strictement plus grand que le deuxième. L'ordre entre deux éléments égaux n'est donc jamais modifié.

Complexité asymptotique

Le tri à bulles est quadratique dans le nombre d'objets à trier. Le nombre d'itération total est n + n-1 + n-2 + ... + 2 ce qui est proportionnel au carré de n.

Localité

Le tri à bulle à un comportement particulièrement indésirable par rapport à la localité. En effet, cet algorithme parcourt le tableau entier à chaque itération. Si la taille du tableau dépasse la taille du cache (ce qui est entièrement possible et assez fréquent), cet algorithme va provoquer un temps linéaire. Pour implémenter cette amélioration, il suffit de maintenir une valeur supplémentaire, l'index à partir duquel l'itération doit démarrer et d'affecter cette valeur la première fois qu'un échange est effectué dans une itération.