Tri à bulles en Python

Exemple de tri à bulles en Python : Présentation étape par étape

Pour mieux comprendre l'algorithme de tri à bulles de Python, examinons en détail un exemple étape par étape, en prenant une liste non triée comme entrée.

Considère la liste suivante comme notre entrée :

• 5
• 1
• 4
• 2
• 8

Nous allons maintenant parcourir les étapes suivies par l'algorithme de tri à bulles pour trier cette liste dans l'ordre croissant :

1. Compare les deux premiers éléments (5 et 1). Puisque 5 > 1, échange-les : 1, 5, 4, 2, 8 2. Passe à la paire suivante (5 et 4). Intervertis-les puisque 5 > 4 : 1, 4, 5, 2, 8 3. Continue le processus avec la paire suivante (5 et 2) et permute-les : 1, 4, 2, 5, 8 4. Passe à la paire suivante (5 et 8). Comme 5 < 8, aucune permutation n'est nécessaire. Puisqu'une passe entière a eu lieu sans qu'aucune permutation ne soit nécessaire, la liste est considérée comme triée et l'algorithme se termine.

Voici une implémentation en code Python de l'algorithme de tri à bulles :

def bubble_sort(arr) : n = len(arr) for i in range(n) : for j in range(0, n - i - 1) : if arr[j] > arr[j + 1] : arr[j], arr[j + 1] = arr[j + 1], arr[j] arr = [5, 1, 4, 2, 8] bubble_sort(arr) print("Sorted array is :", arr)

Implémentation du tri à bulles en Python

L'implémentation de base de l'algorithme de tri à bulles de Python peut être réalisée à l'aide d'une fonction, telle que "bubble_sort", qui prend une liste comme argument et effectue le processus de tri par le biais de boucles imbriquées. La boucle extérieure parcourt tous les éléments de la liste, tandis que la boucle intérieure compare les éléments adjacents et les échange s'ils sont en désordre. La portée de la boucle interne diminue à chaque itération pour éviter de comparer les éléments triés.

Voici un exemple de code Python démontrant la mise en œuvre de base du tri à bulles :

def bubble_sort(arr) : n = len(arr) for i in range(n) : for j in range(0, n - i - 1) : if arr[j] > arr[j + 1] : arr[j], arr[j + 1] = arr[j + 1], arr[j] arr = [64, 34, 25, 12, 22, 11, 90] bubble_sort(arr) print("Sorted array is :", arr)

• Définis une fonction nommée 'bubble_sort' qui prend une liste 'arr' comme entrée.
• Calcule la longueur de la liste (n) à l'aide de la fonction 'len'.
• Utilise une boucle 'for' pour parcourir tous les éléments de la liste (boucle externe).
• À l'aide d'une boucle 'for' imbriquée (boucle interne), parcours les éléments non triés restants et compare les paires adjacentes.
• Si l'élément actuel (arr[j]) est plus grand que l'élément situé à sa droite (arr[j+1]), échange-les à l'aide de l'opération "swap".
• Une fois que les boucles ont fini de s'exécuter, la liste triée 'arr' est imprimée.

Algorithme de tri à bulles Python : Version optimisée

Une version optimisée de l'algorithme de tri à bulles améliore ses performances, en particulier pour les listes partiellement triées ou presque triées. Cette optimisation peut être réalisée en ajoutant une variable qui permet de savoir si des échanges ont eu lieu au cours d'une itération. Si aucune permutation ne se produit, l'algorithme se termine, car la liste est déjà triée. Cette fin anticipée peut faire gagner beaucoup de temps dans certains cas.

Tu trouveras ci-dessous le code Python de la version optimisée du tri à bulles :

def optimised_bubble_sort(arr) : n = len(arr) for i in range(n) : swapped = False for j in range(0, n - i - 1) : if arr[j] > arr[j + 1] : arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped :
            break arr = [64, 34, 25, 12, 22, 11, 90] optimised_bubble_sort(arr) print("Sorted array is :", arr)

• Introduire une variable "swapped" avant la boucle interne pour suivre les échanges effectués pendant chaque itération de la boucle externe.
• La variable 'swapped' est mise à 'True' dans la boucle interne chaque fois qu'une permutation est effectuée.
• Après chaque itération de la boucle intérieure, vérifie la valeur de 'swapped'. Si elle reste 'False', cela signifie qu'aucune permutation n'a été effectuée, ce qui indique que la liste est déjà triée et que l'algorithme peut se terminer prématurément.

Les implémentations de base et optimisées permettent de comprendre l'algorithme de tri à bulles en Python. En les utilisant efficacement dans différents scénarios, tu peux optimiser ton code et obtenir de meilleures performances tout en triant les éléments de tes listes ou tableaux.

Applications de l'algorithme de tri à bulles de Python

L'algorithme Python Bubble Sort est couramment mis en œuvre dans divers scénarios de programmation et de la vie réelle pour sa simplicité, sa facilité de mise en œuvre et sa compréhension. Dans cette section, nous abordons quelques cas d'utilisation où le tri à bulles peut être utilisé efficacement pour trier différents types de données telles que les chaînes de caractères et les applications pratiques en informatique.

Tri à bulles par ordre alphabétique Python : Trier des chaînes de caractères

Le tri à bulles ne se limite pas au tri de valeurs numériques, il peut également être employé pour trier des chaînes de caractères par ordre alphabétique. Pour ce faire, il faut comparer deux éléments de la chaîne de caractères afin de déterminer l'ordre correct. En comparant les valeurs Unicode des caractères de chaque chaîne, le tri à bulles peut classer les chaînes par ordre alphabétique.

Voici une description détaillée du processus :

1. Convertir chaque élément de la chaîne en un caractère de référence, souvent le premier caractère de la chaîne.
2. Compare la valeur Unicode de ces caractères de référence pour décider de l'ordre des deux chaînes.
3. Échange les chaînes si elles se trouvent dans le mauvais ordre d'après leurs caractères de référence.
4. Itère à travers la liste des chaînes, en triant et en échangeant de façon répétée jusqu'à ce que la liste entière soit classée dans l'ordre alphabétique.

Un exemple d'implémentation de code Python pour le tri d'une liste de chaînes de caractères ressemblerait à ceci :

def bubble_sort_strings(arr) : n = len(arr) for i in range(n) : for j in range(0, n - i - 1) : if arr[j] > arr[j + 1] :
                arr[j], arr[j + 1] = arr[j + 1], arr[j] string_list = ["banane", "pomme", "orange", "raisin", "cerise"] bubble_sort_strings(string_list) print("Liste triée alphabétiquement :", string_list)

Avec l'implémentation ci-dessus, la liste de chaînes en entrée est triée par ordre alphabétique sur la base de leur comparaison de caractères de référence, qui dans ce cas est leur premier caractère.

Cas d'utilisation pratique du tri à bulles Python en informatique

Bien que le tri à bulles Python ait ses limites en termes de complexité et d'efficacité, il reste une technique de tri populaire dans diverses applications pratiques où la simplicité et la facilité de mise en œuvre sont plus importantes, notamment dans les cas suivants :

1. Objectifs pédagogiques: Le tri à bulles sert de technique d'introduction pour enseigner les algorithmes de tri aux débutants, car il est facile à comprendre et à mettre en œuvre par rapport à des algorithmes plus complexes tels que le tri par fusion et le tri rapide.

2. Petits ensembles de données: Dans le cas de petits ensembles de données, la simplicité du tri à bulles et ses capacités de tri sur place peuvent l'emporter sur ses inconvénients en termes de performances, ce qui en fait une option appropriée pour trier des quantités relativement faibles de données.

3. Ensemblesde données presque triés: Lorsqu'elle est appliquée à une liste déjà partiellement triée, la version optimisée de l'algorithme de tri à bulles peut se terminer plus tôt, ce qui la rend efficace dans certains scénarios où les données sont déjà dans un état presque trié.

4. Applications dans un environnement restreint: Dans certains cas, les ressources informatiques et la mémoire peuvent être limitées, et l'utilisation d'algorithmes plus complexes n'est pas toujours possible. Dans ces environnements restreints, le tri à bulles peut être une alternative intéressante.

En résumé, le tri à bulles de Python est utile pour des applications spécifiques où la simplicité, la facilité de mise en œuvre et le potentiel éducatif sont prioritaires par rapport à la complexité temporelle. Bien que d'autres algorithmes de tri soient plus efficaces pour les grands ensembles de données ou les structures de données complexes, le tri à bulles continue de servir de solution pratique dans certains cas, notamment pour les nouveaux apprenants en informatique et dans les environnements informatiques contraints.