Le tri à bulles dévoilé avec Python

Introduction

Le tri est une opération fondamentale en informatique, et il existe différents algorithmes pour l'accomplir. L'un des plus simples est le tri à bulles (Bubble Sort). Même s'il n'est pas le plus efficace pour de grands jeux de données, le comprendre est une excellente porte d'entrée vers les principes de base des algorithmes de tri. Dans cet article, on explore ce qu'est le tri à bulles et comment l'implémenter en Python.

C'est quoi le tri à bulles

Le tri à bulles est un algorithme de tri par comparaison qui parcourt la liste à trier de manière répétée. Il compare des éléments adjacents et les échange s'ils sont dans le mauvais ordre. L'algorithme continue d'itérer sur la liste jusqu'à ce qu'aucun échange ne soit nécessaire, signe que la liste est triée.

L'idée centrale : les plus grands éléments « remontent comme des bulles » vers la fin de la liste, tandis que les plus petits « coulent » vers le début.

Comment fonctionne le tri à bulles

Deux versions : pour un enfant, et pour un adulte.

Pour un enfant

Imagine que tu as plein de balles colorées et que tu veux les ranger de la plus légère à la plus lourde. Voici comment ça marche :

1. Comparer et échanger les balles
   • Tu regardes les deux premières balles. Si la première est plus lourde que la seconde, tu les échanges. Maintenant la balle la plus lourde est après la plus légère.
   • Tu passes à la paire suivante et tu fais pareil. Et ainsi de suite pour toutes les paires de ta collection.
2. Une tournée de comparaisons et d'échanges
   • Quand tu as fait toutes les paires, tu remarques que la balle la plus lourde a remonté jusqu'au bout de la rangée.
   • Tu ne touches plus à la plus lourde, elle est à sa place.
   • Tu recommences, mais seulement avec les balles avant la plus lourde. Tu compares et échanges si besoin.
3. Recommencer jusqu'à ce que tout soit trié
   • Tu refais ces tournées de comparaisons et d'échanges, avec à chaque fois de moins en moins de balles à regarder.
   • Tu répètes jusqu'à ce qu'une tournée se passe sans aucun échange. Là, toutes les balles sont rangées !
4. Le tri à bulles, c'est comme des bulles qui remontent
   Le nom vient de l'image des bulles dans une boisson gazeuse. Les plus grosses bulles remontent en premier, les plus petites suivent.

En mots simples, le tri à bulles consiste à ranger des balles colorées en regardant les paires et en les échangeant si elles sont dans le mauvais ordre. On répète jusqu'à ce que les balles soient alignées de la plus légère à la plus lourde, comme les bulles dans ta boisson.

Pour un adulte

Le tri à bulles est un algorithme simple qui parcourt une liste d'éléments (nombres, mots…) de manière répétée, compare chaque paire d'éléments adjacents, et les échange s'ils sont dans le mauvais ordre. Le parcours est répété autant de fois qu'il y a d'éléments dans la liste. Le nom de l'algorithme vient du fait que les petits éléments « remontent comme des bulles d'air dans l'eau » alors que les grands « coulent » vers le bas.

Décomposons :

1. Comparaison et échange
   L'algorithme commence par comparer les deux premiers éléments. Si le premier est plus grand que le second, il les échange. Ce process continue pour chaque paire adjacente.
2. Un passage complet sur la liste
   • Après ce premier passage, le plus grand élément a remonté à la dernière position.
   • L'algorithme refait le même process sur les éléments restants, en excluant le dernier.
3. Répéter jusqu'au tri complet
   • L'algorithme répète ces passages jusqu'à ce qu'aucun échange ne soit nécessaire. Tous les éléments sont alors à leur position triée.
   • À chaque passage, les plus petits éléments « remontent » vers leur position correcte.
4. Optimisation
   Une petite optimisation : un drapeau qui suit si un échange a eu lieu pendant un passage. Si aucun échange n'a eu lieu, la liste est déjà triée et on peut s'arrêter plus tôt.
5. Complexité temporelle
   • Au pire des cas, le tri à bulles demande n passages, où n est le nombre d'éléments. À chaque passage il compare et éventuellement échange des éléments adjacents.
   • Ce qui donne une complexité de O(n²), donc une performance qui s'effondre sur les grandes listes.

En résumé : le tri à bulles est simple conceptuellement et facile à comprendre, mais peu efficace pour les grands jeux de données à cause de sa complexité quadratique. Il sert surtout en pédagogie. En production, on préfère Quick Sort, Merge Sort ou les fonctions de tri intégrées au langage, pour leurs performances bien meilleures.

Implémentation en Python

Voici une implémentation pas à pas du tri à bulles en Python (version optimisée avec drapeau). Le drapeau permet de savoir si un échange a eu lieu pendant une itération. Si non, le tableau est déjà trié et l'algorithme s'arrête plus tôt.

from typing import List, Any

def bubble_sort(collection: List[Any]) -> List[Any]:
    n = len(collection)

    for i in range(n):
        swapped = False  # Initialize the flag
        for j in range(0, n-i-1):
            if collection[j] > collection[j+1]:
                collection[j], collection[j+1] = collection[j+1], collection[j]  # Swap the elements
                swapped = True
        if not swapped:
            break  # No swaps were made, collection is sorted

    return collection

def main():
    # Input collection from the user
    input_str = input("Enter a collection separated by a comma:")
    input_list = [x.strip() for x in input_str.split(',')]

    # Print sorted collection
    print(*bubble_sort(input_list), sep=",")

if __name__ == "__main__":
    main()

L'approche du tri à bulles avec drapeau d'optimisation, en résumé :

1. On suppose au départ qu'aucun échange n'a eu lieu pendant l'itération courante.
2. On parcourt le tableau et compare les éléments adjacents.
3. Si l'élément de gauche est plus grand que celui de droite, on les échange et on positionne le drapeau à vrai.
4. À la fin de la boucle interne, si le drapeau est toujours à faux, le tableau est déjà trié et on peut sortir tôt.
5. On répète les étapes 2 à 4 tant qu'un passage produit au moins un échange.

Cette optimisation réduit potentiellement le nombre d'itérations et de comparaisons quand le tableau est déjà trié ou presque, ce qui rend le tri à bulles légèrement plus efficace.

Applications dans le monde réel

En pratique, le tri à bulles est rarement utilisé en production à cause de son inefficacité par rapport à d'autres algorithmes. Il garde toutefois quelques cas d'usage limités et reste précieux sur le plan pédagogique :

1. Apprentissage : on l'utilise souvent en cours d'algorithmique pour introduire les concepts de tri. Sa simplicité aide les débutants à comprendre comment les algorithmes de tri fonctionnent.
2. Petits jeux de données : si tu n'as que très peu d'éléments à trier, le tri à bulles reste acceptable — ses problèmes de performance ne se voient pas sur les petits tableaux.
3. Données déjà presque triées : si tes données sont déjà majoritairement triées, le côté adaptatif du tri à bulles (il devient plus efficace avec peu d'échanges) peut convenir.
4. Tremplin vers d'autres algorithmes : le tri à bulles est un bon point de départ avant d'attaquer des techniques plus complexes.

Pour la majorité des cas réels — surtout sur de grandes données — on préfère Quick Sort, Merge Sort, ou les fonctions de tri intégrées au langage (par ex. sorted() en Python). Elles offrent des performances bien supérieures et sont mieux adaptées aux applications où la performance compte.

Conclusion

Le tri à bulles est un algorithme de tri basique, fondation pour comprendre les méthodes plus complexes. Ce n'est pas le plus efficace sur les grandes données, mais c'est un excellent point de départ pour apprendre les principes du tri et de l'optimisation d'algorithmes. Plus tu plonges dans l'informatique, plus tu rencontres d'algorithmes avancés aux meilleures performances.

Comprendre le tri à bulles, c'est comme apprendre à faire du vélo avant de passer à la moto. Ça t'équipe d'intuitions précieuses sur les techniques de tri qui te resserviront quand tu exploreras des algorithmes plus sophistiqués.