Python de tri à bulles
Fonctions et méthodes Python
Michael Zippo
01.11.2021
Un tri à bulles Python parcourt une liste et compare les éléments les uns à côté des autres. Si un élément de droite est supérieur à un élément de gauche, les éléments sont permutés. Cela se produit jusqu’à ce que la liste soit triée.
Avez-vous besoin de trier une liste ? Le tri à bulles vous soutient. Le tri à bulles est un type d’algorithme standard qui trie les listes. C’est peut-être le tri le plus simple, il est donc parfait pour les débutants qui découvrent les algorithmes de tri !
Dans ce guide, nous allons discuter du fonctionnement des tris à bulles et de la façon dont vous pouvez implémenter un algorithme de tri à bulles Python. Nous allons passer en revue un exemple afin que vous compreniez comment fonctionne chaque partie d’un tri à bulles.
Tris à bulles Python
Un tri à bulles compare des paires d’éléments adjacents et échange ces éléments si ils ne sont pas en règle. Il est couramment implémenté en Python pour trier des listes de nombres non triés. Les tris à bulles sont un algorithme informatique standard.
En utilisant un tri à bulles, vous pouvez trier les données par ordre croissant ou décroissant. En partant du premier élément d’une liste, un tri à bulles comparera le premier et le deuxième élément. Si le premier élément est supérieur au second, un échange se produit.
Ce processus est répété jusqu’à ce que chaque élément d’une liste soit vérifié. Ensuite, un tri à bulles parcourra à nouveau la liste. Cela se produit jusqu’à ce qu’il n’y ait plus besoin d’effectuer d’échanges.
Quand devriez-vous utiliser un tri à bulles en Python ?
Les tris à bulles sont une bonne méthode de tri à utiliser lorsque vous débutez pour en savoir plus sur les algorithmes de tri. Un tri à bulles est un moyen simple de trier une liste d’éléments qui n’apparaissent pas dans l’ordre.
Les tris à bulles fonctionnent mieux lorsque vous avez une liste avec seulement quelques objets. En effet, lorsqu’un tri à bulles n’a qu’à faire quelques comparaisons, il est très rapide. Lorsque vous devez trier une liste plus importante, vous pouvez utiliser des algorithmes plus efficaces. La plupart des développeurs choisiraient d’utiliser une méthode telle qu’un tri par insertion pour trier une liste d’éléments plus longue.
81 % des participants ont déclaré qu’ils se sentaient plus confiants quant à leurs perspectives d’emploi en technologie après avoir assisté à un bootcamp. Soyez jumelé à un bootcamp aujourd’hui.
Le diplômé moyen d’un bootcamp a passé moins de six mois en transition de carrière, du démarrage d’un bootcamp à la recherche de son premier emploi.
Entrons dans le mauvaises herbes et commencez à comprendre comment fonctionne un tri à bulles. Nous allons commencer par la liste suivante, dont les éléments apparaissent dans le mauvais ordre :
Notre tri à bulles commence par comparer les premier et deuxième éléments de notre liste. Si le premier élément est supérieur au second, alors on échange ces deux éléments.
Dans cet exemple, on va comparer 7 et 19. 7 n’est pas supérieur à 19, donc il reste au même endroit . Notre liste ressemble maintenant à ce qu’elle était auparavant :
Nous allons maintenant comparer les deuxième et troisième éléments de notre liste. 19 est supérieur à 4, ce qui signifie que nous devons les échanger. Notre liste ressemble maintenant à ceci :
Nous pouvons maintenant comparer le troisième et quatrième éléments de notre liste. 19 est supérieur à 12, nous échangeons donc les deux nombres :
Atteindre la fin d’une liste
Notre liste commence déjà à être triée. Mais nous avons atteint la fin de notre liste et elle n’est pas triée. Que se passe-t-il ? Les tris à bulles effectuent plusieurs passages dans une liste, ce qui signifie qu’ils continuent de s’exécuter jusqu’à ce que chaque élément d’une liste soit trié.
Notre tri à bulles recommencera depuis le début jusqu’à ce que la liste soit triée. Nous appelons à chaque fois que la liste commence à trier les valeurs depuis le début une passe. Dans cet exemple, notre tri à bulles comparera 7 et 4. 7 est supérieur à 4, nous échangeons donc les éléments :
Notre algorithme compare 7 et 12. Aucun échange n’est nécessaire, nous allons donc continuer . Nous comparons 12 et 19. Là encore, aucun échange n’est nécessaire. Maintenant que nous avons atteint la fin de notre liste, il est clair qu’il n’y a plus besoin d’échanger.
Avez-vous remarqué que notre algorithme continuait même après le tri de notre liste ? C’est parce qu’un tri à bulles continuera à échanger des éléments jusqu’à ce qu’il compare chaque élément d’une liste pour chaque élément de la liste. Notre algorithme ne s’arrêtera pas tant que chaque échange n’aura pas eu lieu.
Programme Python Bubble Sort
Jusqu’à présent, nous avons échangé des nombres dans un tableau. Il est vrai que nous avons réussi à trier notre liste, mais nous n’avons pas à le faire manuellement. Les tris à bulles sont un algorithme de calcul après tout ; obtenons un ordinateur pour exécuter l’algorithme pour nous.
Notre algorithme commence par une boucle for. Cette boucle parcourt chaque élément de notre tableau. Ensuite, nous utilisons une autre boucle for pour comparer tous les éléments de notre tableau entre eux.
Notre code n’est pas encore terminé. Si vous essayez d’exécuter le programme Python ci-dessus, rien ne se passera. Nous devons appeler notre fonction et lui donner quelques données :
Lorsque nous exécutons notre programme avec cette ligne de code révisée, ce qui suit est renvoyé :
Plus tôt nous avons parlé de la façon dont chaque comparaison possible est faite même si notre liste est triée. Cela rend notre tri à bulles assez inefficace : il continue même après le tri de la liste.
"Career Karma est entré dans ma vie au moment o√π j’en avais le plus besoin et m’a rapidement aidé à participer à un bootcamp. Deux mois après avoir obtenu mon diplôme, j’ai trouvé l’emploi de mes rêves qui correspondait à mes valeurs et à mes objectifs dans la vie !"
Bien que cela ne fasse pas une grande différence dans cet exemple, à grande échelle, cela pourrait avoir un impact sur le temps d’exécution d’un programme. C’est là qu’intervient le tri à bulles optimisé.
Nous pouvons optimiser notre tri à bulles en écrivant une nouvelle variable. Appelons-le swap. Cette variable suivra si des échanges ont eu lieu dans une Python for loop. Si cette variable est définie sur false, cela signifie que notre liste est triée. Plus besoin d’itérations.
