Tri des bulles en Python - Explication du tri à bulles avec l'exemple de code

Introduction au Bubble Sort en Python

Le tri à bulles est un algorithme de tri simple et logique. Son principe de fonctionnement est basé sur l'échange récursif d'éléments adjacents si l'ordre est incorrect. Dans cette rubrique, nous allons en savoir plus sur le tri des bulles en Python.

Le tri à bulles est parfois appelé tri par enfoncement, tri par ondulation.

Voyons cela à travers un exemple:

Première exécution

( 6 1 4 3) -> ( 1 6 4 2): Ici 1 ^er deux éléments sont échangés si l'ordre n'est pas correct.

(1 6 4 2) -> (1 4 6 2): Ici, les deux éléments suivants sont échangés si l'ordre n'est pas correct.

(1 4 6 2 ) -> (1 4 2 6 ): Ici, les deux éléments suivants sont échangés si l'ordre n'est pas correct.

Deuxième manche

( 1 4 2 6) -> ( 1 4 2 6): Ici 1 ^er deux éléments sont comparés, mais n'ont pas été échangés car l'ordre est correct.

(1 4 2 6) -> (1 2 4 6): Ici, les deux éléments suivants sont échangés, car l'ordre n'était pas correct.

(1 2 4 6 ) -> (1 2 4 6 ): Ici, les deux derniers éléments sont comparés, mais n'ont pas été échangés car l'ordre est

Maintenant, nous savons que le tableau semble trié, cependant, une analyse est requise sans aucun échange, à l'algorithme pour savoir si le tri est effectué.

Troisième manche

( 1 2 4 6) -> ( 1 2 4 6): Pas de permutation en 1 ^er élément.

(1 2 4 6) -> (1 2 4 6): Aucun échange dans les deux éléments suivants.

(1 2 4 6 ) -> (1 2 4 6 ): Aucun échange dans les deux derniers éléments.

Comme aucun échange n'a eu lieu à aucun stade, l'algorithme comprend maintenant que le tri est parfait.

Le tri par bulles a son nom parce que les éléments remontent dans le bon ordre, comme des bulles remontant à la surface.

Tri à bulles en langage Python

Voyons maintenant l'implémentation logique du tri à bulles via python. Python est un langage très largement utilisé de nos jours. Le comprendre à l'aide de python vous donnera sûrement la confiance nécessaire pour pouvoir également l'écrire dans d'autres langues.

Code Python

def bubble_Sort(arr): m = len(arr) # Traverse through all the array elements for u in range(m): for v in range(0, mu-1): # traverse the array from 0 to mu-1 # Swap if the element is greater than adjacent next one if arr(v) > arr(v+1) : arr(v), arr(v+1) = arr(v+1), arr(v)

Pour imprimer le tableau après le tri à bulles, vous devez suivre le code:

for i in range(len(arr)): print("%d" %arr(i)), Here arr will be your array.

Explication du code Python

Ici, «m» est la longueur du tableau. Deux boucles for contiennent la logique de masse réelle, où «u» représente le premier élément tandis que «v» représente le second avec lequel le premier élément doit être comparé pour l'échange si l'ordre de tri entre les deux n'est pas correct.

"Arr (v)> arr (v + 1)" ceci représente la comparaison des éléments consécutifs, si le premier élément est supérieur au deuxième élément, l'opération d'échange sera effectuée par l'expression suivante:

C'est-à-dire «arr (v), arr (v + 1) = arr (v + 1), arr (v)».

Cette opération d'échange est appelée swap. La bonne partie est qu'aucune mémoire temporaire n'est requise pour ce type d'opération de swap.

«U» représente la boucle de chaque course, tandis que «v» représente les étapes de chaque étape. Un exemple dans la section ci-dessus peut être cité.

Après avoir effectué le tri à bulles, on peut voir le tableau trié, avec le code mentionné ci-dessous:

for i in range(len(arr)): print ("%d" %arr(i)),

Voyons comment cela se comporte dans Python IDE, pour une compréhension plus approfondie:

Production:

Il y a quelques faits sur Bubble Sort, que tout le monde devrait connaître avant de l'implémenter:

Un tri à bulles est souvent considéré comme une méthode de tri peu efficace. Comme il doit échanger les articles jusqu'à ce que son emplacement final soit connu. Tout cela conduit à un gaspillage des opérations et donc très coûteux. Cet algorithme passe par chaque élément, où le tri est requis ou non. Une fois l'analyse terminée sans échange, le tri des bulles est considéré comme terminé.
C'est la plus simple de toutes les structures de données, pour tout débutant, cela donne une bonne confiance. C'est facile à construire et à comprendre.
Il utilise beaucoup de temps et de mémoire.
Ceci est considéré comme un algorithme stable, car il préserve l'ordre relatif des éléments.
Considéré comme bon pour les petits tableaux / listes. Cependant, c'est une mauvaise idée de l'utiliser pour les longues.

Conclusion

En parcourant le contenu ci-dessus du tri à bulles, on aurait pu avoir une compréhension limpide de cet algorithme de tri, spécialisé avec python. Une fois que l'on se familiarise avec la logique du tri à bulles, la compréhension de l'autre ensemble de structures de données sera alors plus facile. Une approche logique est le seul moyen d'exceller dans le domaine de la structure des données. Comprendre d'abord la logique de l'algorithme de structure de données à chaque étape, puis cibler son code via Python ou dans tout autre langage devrait être le chemin.

Articles recommandés

Ceci est un guide de Bubble Sort en Python. Ici, nous discutons de l'implémentation logique du tri à bulles à travers le code python avec l'explication. Vous pouvez également consulter l'article suivant pour en savoir plus -