Bubble Algorithme de tri avec Python en utilisant un exemple de liste

Qu'est-ce que la Bubble Trier ?

Bubble Trier est un algorithme de tri utilisé pour trier les éléments d'une liste par ordre croissant en comparant deux valeurs adjacentes. Si la première valeur est supérieure à la deuxième valeur, la première valeur prend la deuxième position de valeur, tandis que la deuxième 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 nouvel article concernant notre nouveau projet Bubble Tri dans Python tutoriel tu vas apprendre:

Mettre en œuvre le Bubble Algorithme de tri

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 souhaitons les organiser 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 en les échangeant 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'éléments dans la liste donnée

Étape 2) Déterminez le nombre de passes extérieures (n – 1) à effectuer. Sa longueur est de liste moins un

Étape 3) Effectuez des passes internes (n – 1) fois pour la passe externe 1. Obtenez la valeur du premier élément et comparez-la avec la deuxième valeur. Si la deuxième valeur est inférieure à la première valeur, échangez les positions

Étape 4) Répétez les passes de l’étape 3 jusqu’à atteindre la passe extérieure (n – 1). Obtenez l'élément suivant de la liste, puis répétez le processus effectué à l'étape 3 jusqu'à ce que toutes les valeurs aient été placées dans leur ordre croissant correct.

Étape 5) Renvoie 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 alors rompre la boucle plus tôt.

Optimisé Bubble Algorithme de tri

Par défaut, l'algorithme de tri à bulles dans 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 à bulles nous aide à éviter les itérations inutiles et à é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 indiqué ci-dessous. Bubble Exemple de tri.

L'optimisation se fait en suivant les étapes suivantes

Étape 1) Créez une variable d'indicateur qui surveille si un échange a eu lieu dans la boucle interne

Étape 2) Si les valeurs ont permuté leurs positions, passez à l'itération suivante

Étape 3) Si les bénéfices n’ont pas changé de position, terminez la boucle interne et continuez avec la boucle externe.

Un tri à bulles optimisé est plus efficace car il exécute uniquement les étapes nécessaires et ignore celles qui ne sont pas obligatoires.

Représentation visuelle

Étant donné une liste de cinq éléments, les images suivantes illustrent comment 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 désormais à celle ci-dessus.

Étape 2)

Les valeurs 21 et 9 sont comparées.

21 est supérieur à 9, on échange donc les positions de 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, aucun échange n'a donc lieu.

Étape 4)

Les valeurs 33 et 3 sont comparées pour trouver la plus grande.

La valeur 33 est supérieure à 3, on échange 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

Python Exemples

Le code suivant montre comment implémenter le Bubble Algorithme de tri dans Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Exécution du programme de tri à bulles ci-dessus dans Python produit les résultats suivants

[6, 9, 21, 3, 33]

Explication du code

L'explication du Python Bubble Le code du programme de tri est le suivant

ICI,

1. Définit une fonction bubbleSort qui accepte un paramètre theSeq. Le code ne produit rien.
2. Obtient la longueur du tableau et attribue la valeur à une variable n. Le code ne produit rien
3. Démarre une boucle for qui exécute l'algorithme de tri à bulles (n – 1) fois. C'est la boucle externe. Le code ne produit rien
4. 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
5. 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.
6. 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.
7. Attribue la valeur de theSeq[j] à une variable temporelle tmp si la condition est évaluée comme vraie. Le code ne produit rien
8. La valeur de theSeq[j + 1] est affectée à la position de theSeq[j]. Le code ne produit rien
9. La valeur de la variable tmp est affectée à la position theSeq[j + 1]. Le code ne produit rien
10. La variable flag reçoit la valeur 1 pour indiquer qu'un échange a eu lieu. Le code ne produit rien
11. Utilise une instruction if pour vérifier si la valeur de l'indicateur de variable est 0. Le code ne génère rien
12. Si la valeur est 0, alors nous appelons l'instruction break qui sort de la boucle interne.
13. Renvoie la valeur de theSeq après son tri. Le code génère la liste triée.
14. Définit une variable el qui contient une liste de nombres aléatoires. Le code ne produit rien.
15. Attribue la valeur de la fonction bubbleSort à un résultat variable.
16. Imprime la valeur du résultat variable.

Bubblles avantages du tri

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.

Bubble tri Inconvénients

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 pour des applications réelles.
• Le nombre d'étapes nécessaires pour trier la liste est de l'ordre n²

Analyse de la complexité de Bubble Trier

Il existe trois types de complexité :

1) Trier la complexité

La complexité du tri est utilisée pour exprimer le temps d'exécution et l'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²)

Les complexités temporelles peuvent être classées comme suit :

• Pire cas – c’est ici que la liste fournie est par ordre décroissant. L'algorithme effectue le nombre maximum d'exécutions qui est exprimé par [Big-O] O(n²)
• 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²)

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 échanger les valeurs. Il a donc 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 de gauche est inférieure à la valeur de droite.
• La mise en œuvre d’un algorithme de tri à bulles est relativement simple avec Python. Tout ce que vous devez utiliser sont des boucles for et des instructions if.
• Le problème résolu par l’algorithme de tri à bulles consiste à prendre une liste aléatoire d’éléments et à 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 barboteur a une complexité temporelle de O (n²) et une complexité spatiale de O (1)
• L’algorithme de tri par barboteur est mieux adapté à des fins académiques qu’à des applications du monde réel.
• Le tri à bulles optimisé rend l'algorithme plus efficace en sautant les itérations inutiles lors de la vérification des valeurs déjà triées.