L’algorithme de tri à bulles nécessite une paire de boucles imbriquées. La boucle externe doit itérer une fois pour chaque élément de l’ensemble de données (de taille n) tandis que la boucle interne effectue une itération n fois la première fois qu’elle est entrée, n-1 fois la seconde, et ainsi de suite. Considérez le but de chaque boucle. Comme expliqué ci-dessus, le tri à bulles est structuré de telle sorte qu’à chaque passage dans la liste, l’élément le plus grand suivant des données est déplacé à sa place appropriée. Par conséquent, pour obtenir tous les n éléments à leur place correcte, la boucle externe doit être exécutée n fois.
La boucle interne est exécutée à chaque itération de la boucle externe. Son objectif est de mettre en place l’élément le plus important suivant. La boucle interne effectue donc la comparaison et l’échange d’éléments adjacents. Pour déterminer la complexité de cette boucle, nous calculons le nombre de comparaisons à effectuer. Lors de la première itération de la boucle externe, en essayant de placer le plus grand élément, il doit y avoir n – 1 comparaisons: la première comparaison est faite entre les premier et deuxième éléments, la deuxième est faite entre les deuxième et troisième éléments, et ainsi de suite jusqu’à ce que la n-1e comparaison soit faite entre le n-1e et le nième élément. Lors de la deuxième itération de la boucle externe, il n’est pas nécessaire de comparer le avec le dernier élément de la liste, car il a été placé au bon endroit lors de la passe précédente. Par conséquent, la deuxième itération ne nécessite que n-2 comparaisons. Ce modèle continue jusqu’à l’avant-dernière itération de la boucle externe lorsque seuls les deux premiers éléments de la liste ne sont pas triés; clairement dans ce cas, une seule comparaison est nécessaire. Le nombre total de comparaisons est donc (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 ou O (n2).
Le meilleur cas pour le tri par bulles se produit lorsque la liste est déjà triée ou presque triée. Dans le cas où la liste est déjà triée, le tri à bulles se terminera après la première itération, car aucun échange n’a été effectué. Chaque fois qu’un passage est effectué dans la liste et qu’aucun échange n’a été effectué, il est certain que la liste est triée. Le tri à bulles est également efficace lorsqu’un élément aléatoire doit être trié dans une liste triée, à condition que le nouvel élément soit placé au début et non à la fin. Lorsqu’il est placé au début, il va simplement remonter au bon endroit, et la deuxième itération dans la liste générera 0 swaps, mettant fin au tri. Rappelez-vous que si l’élément aléatoire est placé à la fin, le tri à bulles perd de son efficacité car chaque élément plus grand que celui-ci doit faire des bulles jusqu’en haut.
Le pire des cas absolus pour le tri à bulles est lorsque le le plus petit élément de la liste est à la grande extrémité. Parce que dans chaque itération, seul le plus grand élément non trié est placé à son emplacement approprié, lorsque le plus petit élément est à la fin, il devra être échangé à chaque fois dans la liste, et il n’ira pas au début de la liste jusqu’à ce que tout n des itérations ont eu lieu. Dans le pire des cas, il faut n itérations de n / 2 swaps pour que l’ordre soit, encore une fois, n2.
Meilleur cas: nCas moyen: n2Pire cas: n2