Qu'est-ce qu'un tri à bulles?
Bubble Sort est un algorithme de tri utilisé pour trier les éléments de liste par ordre croissant en comparant deux valeurs adjacentes. Si la première valeur est supérieure à la seconde valeur, la première valeur prend la seconde position de valeur, tandis que la seconde valeur prend la première position de valeur. Si la première valeur est inférieure à la deuxième valeur, aucun échange n'est effectué.
Ce processus est répété jusqu'à ce que toutes les valeurs d'une liste aient été comparées et échangées si nécessaire. Chaque itération est généralement appelée une passe. Le nombre de passes dans un tri à bulles est égal au nombre d'éléments dans une liste moins un.
Dans ce didacticiel sur le tri des bulles en Python, vous apprendrez:
- Qu'est-ce qu'un tri à bulles?
- Implémentation de l'algorithme de tri à bulles
- Algorithme de tri à bulles optimisé
- Représentation visuelle
- Exemples Python
- Explication du code
- Avantages du tri à bulles
- Inconvénients du tri à bulles
- Analyse de complexité du tri à bulles
Implémentation de l'algorithme de tri à bulles
Nous décomposerons l'implémentation en trois (3) étapes, à savoir le problème, la solution et l'algorithme que nous pouvons utiliser pour écrire du code pour n'importe quel langage.
Le problème
Une liste d'articles est donnée dans un ordre aléatoire, et nous aimerions organiser les articles de manière ordonnée
Considérez la liste suivante:
[21,6,9,33,3]
La solution
Parcourez la liste en comparant deux éléments adjacents et permutez-les si la première valeur est supérieure à la deuxième valeur.
Le résultat devrait être le suivant:
[3,6,9,21,33]
Algorithme
L'algorithme de tri à bulles fonctionne comme suit
Étape 1) Obtenez le nombre total d'éléments. Obtenez le nombre total d'articles dans la liste donnée
Étape 2) Déterminez le nombre de passes extérieures (n - 1) à effectuer. Sa longueur est la liste moins un
Étape 3) Effectuer des passes internes (n - 1) fois pour la passe externe 1. Obtenez la première valeur d'élément et comparez-la avec la deuxième valeur. Si la deuxième valeur est inférieure à la première valeur, permutez les positions
Étape 4) Répétez l'étape 3 passes jusqu'à ce que vous atteigniez la passe extérieure (n - 1). Obtenez l'élément suivant dans la liste, puis répétez le processus qui a été effectué à l'étape 3 jusqu'à ce que toutes les valeurs aient été placées dans leur ordre croissant correct.
Étape 5) Renvoyez le résultat lorsque toutes les passes ont été effectuées. Renvoie les résultats de la liste triée
Étape 6) Optimiser l'algorithme
Évitez les passes internes inutiles si la liste ou les valeurs adjacentes sont déjà triées. Par exemple, si la liste fournie contient déjà des éléments qui ont été triés par ordre croissant, nous pouvons interrompre la boucle tôt.
Algorithme de tri à bulles optimisé
Par défaut, l'algorithme de tri à bulles en Python compare tous les éléments de la liste, que la liste soit déjà triée ou non. Si la liste donnée est déjà triée, comparer toutes les valeurs est une perte de temps et de ressources.
L'optimisation du tri des bulles nous permet d'éviter les itérations inutiles et d'économiser du temps et des ressources.
Par exemple, si les premier et deuxième éléments sont déjà triés, il n'est pas nécessaire de parcourir le reste des valeurs. L'itération est terminée et la suivante est lancée jusqu'à ce que le processus soit terminé, comme illustré dans l'exemple de tri à bulles ci-dessous.
L'optimisation se fait en suivant les étapes suivantes
Étape 1) Créez une variable d'indicateur qui surveille si un échange s'est produit dans la boucle interne
Étape 2) Si les valeurs ont des positions permutées, passez à l'itération suivante
Étape 3) Si les avantages n'ont pas permuté de positions, terminez la boucle interne et continuez avec la boucle externe.
Un tri de bulles optimisé est plus efficace car il n'exécute que les étapes nécessaires et ignore celles qui ne le sont pas.
Représentation visuelle
Étant donné une liste de cinq éléments, les images suivantes illustrent la façon dont le tri à bulles parcourt les valeurs lors de leur tri
L'image suivante montre la liste non triée
Première itération
Étape 1)
Les valeurs 21 et 6 sont comparées pour vérifier laquelle est supérieure à l'autre.
21 est supérieur à 6, donc 21 prend la position occupée par 6 tandis que 6 prend la position qui était occupée par 21
Notre liste modifiée ressemble maintenant à celle ci-dessus.
Étape 2)
Les valeurs 21 et 9 sont comparées.
21 est supérieur à 9, nous échangeons donc les positions 21 et 9
La nouvelle liste est maintenant comme ci-dessus
Étape 3)
Les valeurs 21 et 33 sont comparées pour trouver la plus grande.
La valeur 33 est supérieure à 21, donc aucun échange n'a lieu.
Étape 4)
Les valeurs 33 et 3 sont comparées pour trouver la plus grande.
La valeur 33 est supérieure à 3, nous échangeons donc leurs positions.
La liste triée à la fin de la première itération est comme celle ci-dessus
Deuxième itération
La nouvelle liste après la deuxième itération est la suivante
Troisième itération
La nouvelle liste après la troisième itération est la suivante
Quatrième itération
La nouvelle liste après la quatrième itération est la suivante
Exemples Python
Le code suivant montre comment implémenter l'algorithme de tri à bulles en Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
L'exécution du programme de tri de bulles ci-dessus en Python produit les résultats suivants
[6, 9, 21, 3, 33]
Explication du code
L'explication du code du programme Python Bubble Sort est la suivante
ICI,
- Définit une fonction bubbleSort qui accepte un paramètre theSeq. Le code ne produit rien.
- Obtient la longueur du tableau et affecte la valeur à une variable n. Le code ne produit rien
- Démarre une boucle for qui exécute l'algorithme de tri à bulles (n - 1) fois. C'est la boucle extérieure. Le code ne produit rien
- Définit une variable d'indicateur qui sera utilisée pour déterminer si un échange a eu lieu ou non. Ceci est à des fins d'optimisation. Le code ne produit rien
- Démarre la boucle interne qui compare toutes les valeurs de la liste de la première à la dernière. Le code ne produit rien.
- Utilise l'instruction if pour vérifier si la valeur du côté gauche est supérieure à celle du côté droit immédiat. Le code ne produit rien.
- Affecte la valeur de theSeq [j] à une variable temporelle tmp si la condition est évaluée à true. Le code ne produit rien
- La valeur de theSeq [j + 1] est affectée à la position de theSeq [j]. Le code ne produit rien
- La valeur de la variable tmp est affectée à la position theSeq [j + 1]. Le code ne produit rien
- La variable indicateur reçoit la valeur 1 pour indiquer qu'un échange a eu lieu. Le code ne produit rien
- Utilise une instruction if pour vérifier si la valeur de l'indicateur de variable est 0. Le code ne produit rien
- Si la valeur est 0, nous appelons l'instruction break qui sort de la boucle interne.
- Renvoie la valeur de theSeq après son tri. Le code produit la liste triée.
- Définit une variable el qui contient une liste de nombres aléatoires. Le code ne produit rien.
- Affecte la valeur de la fonction bubbleSort à un résultat variable.
- Imprime la valeur du résultat de la variable.
Avantages du tri à bulles
Voici quelques-uns des avantages de l'algorithme de tri à bulles
- C'est facile à comprendre
- Il fonctionne très bien lorsque la liste est déjà ou presque triée
- Il ne nécessite pas de mémoire étendue.
- Il est facile d'écrire le code de l'algorithme
- Les besoins en espace sont minimes par rapport aux autres algorithmes de tri.
Inconvénients du tri à bulles
Voici quelques-uns des inconvénients de l'algorithme de tri à bulles
- Il ne fonctionne pas bien lors du tri de grandes listes. Cela prend trop de temps et de ressources.
- Il est principalement utilisé à des fins académiques et non dans le monde réel.
- Le nombre d'étapes nécessaires pour trier la liste est de l'ordre n 2
Analyse de complexité du tri à bulles
Il existe trois types de complexité:
1) Trier la complexité
La complexité de tri est utilisée pour exprimer la quantité de temps d'exécution et d'espace nécessaire pour trier la liste. Le tri à bulles effectue (n - 1) itérations pour trier la liste où n est le nombre total d'éléments dans la liste.
2) Complexité temporelle
La complexité temporelle du tri à bulles est O (n 2 )
Les complexités temporelles peuvent être classées comme suit:
- Pire des cas - c'est là que la liste fournie est dans l'ordre décroissant. L'algorithme effectue le nombre maximum d'exécutions qui est exprimé par [Big-O] O (n 2 )
- Meilleur cas - cela se produit lorsque la liste fournie est déjà triée. L'algorithme effectue le nombre minimum d'exécutions qui est exprimé par [Big-Omega] Ω (n)
- Cas moyen - cela se produit lorsque la liste est dans un ordre aléatoire. La complexité moyenne est représentée par [Big-theta] ⊝ (n 2 )
3) Complexité spatiale
La complexité de l'espace mesure la quantité d'espace supplémentaire nécessaire pour trier la liste. Le tri à bulles ne nécessite qu'un (1) espace supplémentaire pour la variable temporelle utilisée pour permuter les valeurs. Par conséquent, il a une complexité spatiale de O (1).
Résumé
- L'algorithme de tri à bulles fonctionne en comparant deux valeurs adjacentes et en les échangeant si la valeur à gauche est inférieure à la valeur à droite.
- L'implémentation d'un algorithme de tri à bulles est relativement simple avec Python. Tout ce que vous devez utiliser, ce sont les boucles for et les instructions if.
- Le problème que l'algorithme de tri à bulles résout est de prendre une liste aléatoire d'éléments et de la transformer en une liste ordonnée.
- L'algorithme de tri à bulles dans la structure de données fonctionne mieux lorsque la liste est déjà triée car il effectue un nombre minimal d'itérations.
- L'algorithme de tri à bulles ne fonctionne pas bien lorsque la liste est dans l'ordre inverse.
- Le tri bubbler a une complexité temporelle de O (n 2 ) et une complexité spatiale de O (1)
- L'algorithme de tri par bulleur est le mieux adapté à des fins académiques et non à des applications du monde réel.
- Le tri optimisé des bulles rend l'algorithme plus efficace en sautant les itérations inutiles lors de la vérification des valeurs qui ont déjà été triées.