Python de tri à bulles

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 :

719412

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 :

7 19412

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 :

741912

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 :

741219

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.

Commençons par écrire une fonction Python qui trie une liste de nombres par ordre croissant :

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.

Dans notre code, nous avons défini une instruction Python "if‚" qui vérifie si un élément donné est plus grand que l’élément suivant dans la liste. Cette instruction "if" effectuera des comparaisons telles que :

  • Est le premier élément de t La liste est-elle supérieure au deuxième ?
  • Le deuxième élément de la liste est-il supérieur au troisième ?

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 :

Notre code renvoie :

Nous l’avons fait ! Notre tableau Python est trié par ordre croissant ! Vous pouvez utiliser un tri à bulles pour trier une liste par ordre décroissant. Pour ce faire, remplacez le signe supérieur à par un signe inférieur à dans le Python "if‚" déclaration :

Lorsque nous exécutons notre programme avec cette ligne de code révisée, ce qui suit est renvoyé :

Optimiser le tri à bulles

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 !"

Venus, ingénieur logiciel chez Rockbot

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.

Révisons notre fonction sortList d’avant :

Nous avons défini une variable appelée swap qui a la valeur par défaut : True. Elle est contenue dans notre première boucle for car elle permet de savoir si un échange s’est produit à chaque passage dans la liste. Si notre tableau fait une comparaison, la valeur de swap est définie sur False.

S’il n’y a pas de swap effectué lors du dernier swap, alors le tableau est déjà trié. Notre liste vérifiera alors si swap est égal à True. Si c’est s, notre programme cessera de s’exécuter.

Exécutons à nouveau notre code :

Nos données ont été triées de la même manière mais notre algorithme est désormais plus rapide et plus efficace. Notre algorithme s’arrête maintenant dès que tous les éléments de la liste ont été triés.

Analyse de la complexité

La complexité temporelle moyenne du tri à bulles est de O(n^2). Cela se produit lorsque les éléments d’un tableau ne sont pas triés.

Dans le pire des cas, un tri à bulles s’exécute à O(n^2). Cela se produit lorsqu’un tableau est déjà dans l’ordre croissant ou décroissant et doit être trié dans le sens inverse. Dans le meilleur des cas, cet algorithme fonctionnera en O(n). Cela se produit si un tableau est déjà trié.

Pour en savoir plus sur la complexité des algorithmes, consultez notre Career Karma guide Big O Notation.

Conclusion

Les tris à bulles offrent un moyen simple de trier une liste de données. Ils peuvent être utilisés pour trier les données par ordre croissant ou décroissant.

Cet algorithme est le plus souvent utilisé lorsque vous devez trier une petite liste. Les tris à bulles sont une bonne introduction aux algorithmes de tri. Vous pouvez les utiliser pour vous familiariser avec les algorithmes avant de découvrir des méthodes de tri plus avancées, telles qu’un tri par insertion.

Pour obtenir des conseils d’experts sur les ressources et les cours Python, consultez notre Guide d’apprentissage de Python.