Bubble Sort est un algorithme de tri simple qui parcourt la liste à plusieurs reprises, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Il est nommé « Tri à bulles » car les éléments plus petits « bullent » en haut de la liste. Bien qu’il ne s’agisse pas de l’algorithme de tri le plus efficace, il est facile à comprendre et à mettre en œuvre, ce qui en fait un bon point de départ pour en apprendre davantage sur les algorithmes de tri. Dans cet article, nous approfondirons le concept de Bubble Sort, fournirons une implémentation Python avec sortie et discuterons de la complexité temporelle de l'algorithme.
Comprendre le tri à bulles
L'idée de base derrière Bubble Sort est de parcourir la liste plusieurs fois, en comparant les éléments adjacents et en les échangeant s'ils sont dans le désordre. Le processus se poursuit jusqu'à ce qu'aucun échange ne soit plus nécessaire, indiquant que la liste est désormais triée. L'algorithme tire son nom de la façon dont les éléments plus petits se déplacent progressivement vers le haut de la liste, un peu comme des bulles remontant à la surface.
Décomposons les étapes de l'algorithme Bubble Sort :
- Parcourez la liste : commencez par le début de la liste et comparez chaque paire d’éléments adjacents.
- Comparez et échangez : si les éléments sont dans le mauvais ordre, échangez-les. Cela garantit que le plus grand élément « bouillonne » et que le plus petit descend.
- Continuer l'itération : répétez le processus pour chaque paire d'éléments adjacents jusqu'à ce que la fin de la liste soit atteinte.
- Répétez jusqu'à ce que le tri soit effectué : continuez à parcourir la liste jusqu'à ce que plus aucun échange ne soit nécessaire. À ce stade, la liste est triée.
Bien que Bubble Sort soit simple à comprendre, il ne s’agit pas de l’algorithme de tri le plus efficace, en particulier pour les grands ensembles de données. Sa complexité temporelle est O(n^2) dans le pire des cas, où « n » est le nombre d'éléments dans la liste. Cette complexité temporelle quadratique le rend moins adapté aux grands ensembles de données que les algorithmes de tri plus avancés.
Implémentation Python du tri à bulles
Maintenant, implémentons Bubble Sort en Python et observons son comportement avec un exemple de liste :
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
Dans cette implémentation, la fonction bubble_sort prend une liste (arr) comme paramètre et la trie sur place. La boucle imbriquée compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. La boucle externe garantit que le processus est répété jusqu'à ce que la liste entière soit triée.
Résultat et explication
Exécutons le code Python fourni avec la liste d'exemples et observons le résultat :
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Ici, la liste originale [64, 34, 25, 12, 22, 11, 90] est triée avec succès à l'aide de l'algorithme Bubble Sort, ce qui donne la liste triée [11, 12, 22, 25, 34, 64, 90].
L'algorithme parcourt la liste plusieurs fois, en comparant et en échangeant les éléments jusqu'à ce que la liste entière soit triée. À chaque passage, le plus gros élément non trié « bouillonne » jusqu'à sa position correcte. Ce processus se poursuit jusqu'à ce qu'aucun échange ne soit plus nécessaire, indiquant que la liste est entièrement triée.
Bien que Bubble Sort trie avec succès la liste, il est important de noter que sa complexité temporelle le rend moins efficace pour les grands ensembles de données par rapport à d'autres algorithmes de tri tels que le tri par fusion ou le tri rapide.
Complexité temporelle du tri à bulles
Comprendre la complexité temporelle d’un algorithme est crucial pour évaluer son efficacité, en particulier lorsqu’il s’agit de grands ensembles de données. La complexité temporelle du tri à bulles est O(n^2) dans le pire des cas, où « n » est le nombre d'éléments dans la liste.
Décomposons l'analyse de la complexité temporelle :
- La boucle externe s'exécute sur « n » itérations, où « n » est le nombre d'éléments dans la liste.
- La boucle interne s'exécute également pendant 'n' itérations dans le pire des cas. Cependant, à mesure que l'algorithme progresse, le nombre d'itérations dans la boucle interne diminue, à mesure que le plus grand élément non trié est placé à sa position correcte à chaque passage.
- Dans le pire des cas, le nombre de comparaisons et d'échanges est proportionnel au carré du nombre d'éléments dans la liste, ce qui entraîne une complexité temporelle O(n^2). Cela rend le tri à bulles inefficace pour les grands ensembles de données, et des algorithmes de tri plus avancés avec de meilleures complexités temporelles sont souvent préférés dans les applications du monde réel.
Conclusion
Dans cet article, nous avons exploré le concept de Bubble Sort, un algorithme de tri simple qui compare et échange à plusieurs reprises les éléments adjacents jusqu'à ce que la liste entière soit triée. Nous avons fourni une implémentation Python de Bubble Sort, l'avons exécutée avec un exemple de liste et analysé le résultat. De plus, nous avons discuté de la complexité temporelle du tri à bulles, en soulignant sa complexité temporelle O(n^2) dans le pire des cas et ses implications sur l'efficacité.