Principe de l'Algorithme de Tri à Bulles
L'algorithme de tri à bulles fonctionne comme suit :
Initialisation : On commence par définir un tableau (ou une liste) de données à trier, dans cet exemple représenté par le tableau t. On a également besoin de quelques variables pour stocker des indices et des valeurs temporaires.
Boucle de Lecture : On lit les éléments du tableau à trier à partir de l'entrée standard (dans cet exemple, avec un maximum de N éléments).
Boucle de Tri : La partie principale de l'algorithme est la boucle Tant que. Cette boucle s'exécute tant qu'il y a des échanges à effectuer dans le tableau. Initialement, i est défini sur la dernière position du tableau.
Boucle d'Échange : À l'intérieur de la boucle Tant que, une autre boucle Pour parcourt les éléments du tableau de gauche à droite (deuxième élément jusqu'à l'élément actuel i). Si un élément est plus petit que l'élément précédent, les deux éléments sont échangés.
Réduction de i : Après avoir parcouru le tableau une fois, i est réduit d'une unité (i ← i - 1). Cela signifie que lors de la prochaine itération de la boucle Tant que, la dernière position du tableau (où l'élément le plus grand est maintenant situé) est ignorée car elle est déjà triée.
Fin de la Boucle : La boucle Tant que se répète jusqu'à ce que i atteigne 1, ce qui signifie que tout le tableau a été trié.
Affichage : Une fois que le tri est terminé, le tableau trié est affiché à l'écran.
Complexité de l'Algorithme de Tri à Bulles
L'algorithme de tri à bulles a une complexité temporelle de O(n^2) dans le pire cas, ce qui signifie que son temps d'exécution augmente quadratiquement avec la taille du tableau. Cela en fait un algorithme inefficace pour de grandes quantités de données.
La raison de cette inefficacité est que même si une grande partie du tableau est déjà triée, l'algorithme effectue toujours des comparaisons et des échanges inutiles à chaque itération.
Cependant, le tri à bulles a l'avantage d'être simple à implémenter et de nécessiter très peu d'espace mémoire supplémentaire. Il peut donc être utile dans des cas spécifiques où la simplicité de l'algorithme est privilégiée par rapport à la performance.
En résumé, le tri à bulles est un algorithme de tri basique qui fonctionne par comparaison et échange d'éléments adjacents jusqu'à ce que tout le tableau soit trié. Bien qu'il soit peu efficace pour de grandes quantités de données, il est utile pour comprendre les concepts fondamentaux des algorithmes de tri.