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

Qu'est-ce que la Bubble Trier ?

Bubble Trier L'algorithme de tri par ordre croissant compare deux valeurs adjacentes. Si la première valeur est supérieure à la seconde, elle prend la place de la seconde, et inversement. Si la première valeur est inférieure à la seconde, elles restent en place.ping est fait.

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 Vous découvrirez le problème qu'il résout, sa forme optimisée, une présentation visuelle étape par étape et un exemple de fonctionnement. Python programme et ses caractéristiques de performance.

Mettre en œuvre le Bubble Algorithme de tri

Nous allons décomposer 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 les ranger 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.ping les retenir si la première valeur est supérieure à la seconde.

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 égale à la liste moins un.

Étape 3) Effectuez (n – 1) passes internes pour la passe externe 1. Récupérez la valeur du premier élément et comparez-la avec celle du deuxième. Si la deuxième valeur est inférieure à la première, inversez leurs positions.

Étape 4) Répétez l'étape 3 jusqu'à atteindre le passage extérieur (n – 1). Prenez l'élément suivant dans la liste, puis répétez le processus effectué à l'étape 3 jusqu'à ce que toutes les valeurs soient placées dans leur ordre croissant correct.

Étape 5) Renvoie le résultat une fois tous les passages effectués. Renvoie 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 s'effectue en suivant les étapes suivantes :

Étape 1) Créez une variable indicateur qui surveille si un échange a lieu.ping cela s'est produit dans la boucle interne.

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

Étape 3) Si les valeurs n'ont pas échangé leurs positions, terminez la boucle interne et poursuivez 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 du 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, donc nous échangeons les positions de 21 et 9.

La nouvelle liste est désormais celle 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 pas d'échangeping a 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 semblable à 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

Voici la nouvelle liste après la quatrième itération :

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 :

[3, 6, 9, 21, 33]

Code Explication

L'explication du Python BubblLe 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. Récupère la longueur du tableau et assigne cette valeur à une variable n. Le code n'affiche rien.
3. Lance une boucle `for` qui exécute l'algorithme de tri à bulles (n – 1) fois. Il s'agit de la boucle externe. Le code ne produit aucun affichage.
4. Définit une variable indicateur permettant de déterminer si un échange a eu lieu ou non. Ceci à des fins d'optimisation. Le code ne produit aucune sortie.
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. Si la condition est vraie, la valeur de theSeq[j] est affectée à la variable temporaire tmp. Ce code ne produit aucun affichage.
8. La valeur de theSeq[j + 1] est affectée à la position de theSeq[j]. Le code ne produit aucun résultat.
9. La valeur de la variable tmp est affectée à la position theSeq[j + 1]. Le code ne produit aucun résultat.
10. La variable indicateur prend la valeur 1 pour signaler qu'un échange a eu lieu. Le code n'affiche rien.
11. Utilise une instruction if pour vérifier si la valeur de la variable flag est 0. Le code n'affiche 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 avantages de l'algorithme de tri à bulles :

• C'est facile à comprendre.
• Il fonctionne très bien lorsque la liste est déjà triée ou presque.
• 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 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 concrètes.
• 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 exprime le temps d'exécution et l'espace mémoire nécessaires pour trier une liste. Le tri à bulles effectue (n – 1) itérations pour trier la liste, où n représente le nombre total d'éléments.

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 minimal d'exécutions, exprimé par Ω(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é spatiale mesure l'espace supplémentaire nécessaire au tri de la liste. Le tri à bulles ne requiert qu'un seul espace supplémentaire (1) pour la variable temporelle utilisée pour l'échange.ping valeurs. Par conséquent, sa complexité spatiale est de O(1).

FAQ