Numérique et Sciences Informatiques > Algorithmique : Tris et Recherche > Algorithmes de Tri Élémentaires > Tri à bulles

Le Tri à Bulles: Comprendre et Implémenter Facilement

Apprenez le tri à bulles, un algorithme de tri simple mais fondamental en informatique. Cette page vous guide à travers le concept, l'implémentation et les limitations du tri à bulles, avec des exemples clairs et des explications détaillées pour les élèves de lycée (NSI).

Introduction au Tri à Bulles

Le tri à bulles, aussi connu sous le nom de bubble sort, est un algorithme de tri simple qui parcourt répétitivement la liste à trier, compare chaque paire d'éléments adjacents et les échange si ils sont dans le mauvais ordre. Le passage à travers la liste est répété jusqu'à ce qu'aucun échange ne soit nécessaire, ce qui indique que la liste est triée. C'est un algorithme d'apprentissage idéal pour comprendre les bases du tri, bien qu'il ne soit pas très efficace pour les grandes listes.

Principe de Fonctionnement

Le tri à bulles fonctionne en comparant chaque élément avec son voisin direct. Si l'élément de gauche est plus grand que celui de droite (pour un tri croissant), alors ils sont échangés. Cette opération 'fait remonter' l'élément le plus grand vers la fin de la liste, comme une bulle qui monte à la surface. Après chaque passage complet dans la liste, le plus grand élément non trié est placé à sa position correcte à la fin de la liste. On répète le processus sur la partie non triée de la liste jusqu'à ce qu'elle soit entièrement triée.

Exemple: Prenons la liste [5, 1, 4, 2, 8].

  1. Premier passage: (5, 1, 4, 2, 8) -> (1, 5, 4, 2, 8) puis (1, 5, 4, 2, 8) -> (1, 4, 5, 2, 8) puis (1, 4, 5, 2, 8) -> (1, 4, 2, 5, 8) puis (1, 4, 2, 5, 8) -> (1, 4, 2, 5, 8). 8 est maintenant à sa place.
  2. Deuxième passage: (1, 4, 2, 5, 8) -> (1, 4, 2, 5, 8) puis (1, 4, 2, 5, 8) -> (1, 2, 4, 5, 8) puis (1, 2, 4, 5, 8). 5 est maintenant à sa place.
  3. Troisième passage: (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8) puis (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8). 4 est maintenant à sa place.
  4. Quatrième passage: (1, 2, 4, 5, 8) -> (1, 2, 4, 5, 8). 2 est maintenant à sa place.
La liste est maintenant triée: [1, 2, 4, 5, 8].

Implémentation en Python

Voici un exemple d'implémentation du tri à bulles en Python: 

def tri_a_bulles(liste):
    n = len(liste)
    for i in range(n):
        # Le dernier i éléments sont déjà triés
        for j in range(0, n-i-1):
            # Parcourir le tableau de 0 à n-i-1
            # Echanger si l'élément trouvé est plus grand
            # que l'élément suivant
            if liste[j] > liste[j+1] :
                liste[j], liste[j+1] = liste[j+1], liste[j]

Ce code parcourt la liste et compare chaque paire d'éléments adjacents. Si ils sont dans le mauvais ordre, ils sont échangés. La boucle externe assure que ce processus est répété pour chaque élément de la liste. Le paramètre n-i-1 dans la boucle interne réduit le nombre de comparaisons à chaque passage, car les derniers éléments sont déjà triés.

Optimisation du Tri à Bulles

Le tri à bulles peut être optimisé en arrêtant l'algorithme s'il n'y a pas d'échanges lors d'un passage. Cela signifie que la liste est déjà triée, et il est inutile de continuer à parcourir la liste.

Voici l'implémentation optimisée en Python:

def tri_a_bulles_optimise(liste):
    n = len(liste)
    for i in range(n):
        # Booléen pour vérifier si un échange a eu lieu
        echange = False
        for j in range(0, n-i-1):
            if liste[j] > liste[j+1] :
                liste[j], liste[j+1] = liste[j+1], liste[j]
                echange = True
        # Si aucun échange n'a eu lieu, la liste est triée
        if echange == False:
            break

Cette optimisation peut améliorer significativement les performances du tri à bulles sur les listes qui sont presque triées ou déjà triées.

Complexité Algorithmique

Le tri à bulles a une complexité temporelle de O(n²) dans le pire des cas et en moyenne, où n est le nombre d'éléments dans la liste. Dans le meilleur des cas (liste déjà triée avec l'optimisation), la complexité est de O(n). En termes de complexité spatiale, le tri à bulles est un algorithme 'en place' (in-place), ce qui signifie qu'il ne nécessite qu'un espace mémoire constant supplémentaire (O(1)), indépendamment de la taille de la liste à trier.

Avantages et Inconvénients

Avantages:

  • Simple à comprendre et à implémenter.
  • Facile à déboguer.
  • Nécessite peu de mémoire (algorithme 'en place').
  • Efficace pour les petites listes.
  • Peut détecter rapidement si une liste est déjà triée (avec l'optimisation).
Inconvénients:
  • Très inefficace pour les grandes listes.
  • Complexité temporelle quadratique (O(n²)) dans le cas moyen et le pire cas.
  • Pas adapté pour les applications qui nécessitent un tri rapide.
En résumé, le tri à bulles est un bon algorithme pour l'apprentissage et pour trier de petites listes, mais il est préférable d'utiliser des algorithmes plus efficaces comme le tri rapide (quicksort) ou le tri fusion (mergesort) pour les grandes listes.

Ce qu'il faut retenir

  • Le tri à bulles compare et échange les éléments adjacents pour 'faire remonter' les éléments les plus grands.
  • L'algorithme parcourt la liste plusieurs fois jusqu'à ce qu'aucun échange ne soit nécessaire.
  • La complexité temporelle est de O(n²) dans le cas moyen et le pire cas, et O(n) dans le meilleur cas (optimisé).
  • La complexité spatiale est de O(1) (algorithme 'en place').
  • Le tri à bulles est simple à comprendre mais inefficace pour les grandes listes.

← Le Tri par Sélection : Une Méthode de Tri Simple et Efficace Optimisation de la Recherche Linéaire →

FAQ

  • Quand devrais-je utiliser le tri à bulles?

    Le tri à bulles est approprié pour les petites listes où la simplicité du code est plus importante que l'efficacité. Il peut également être utile pour l'apprentissage des algorithmes de tri.
  • Comment puis-je améliorer les performances du tri à bulles?

    Vous pouvez améliorer les performances en ajoutant une optimisation qui arrête l'algorithme si aucun échange n'a lieu lors d'un passage. Cela indique que la liste est déjà triée.
  • Le tri à bulles est-il stable?

    Oui, le tri à bulles est un algorithme de tri stable, ce qui signifie qu'il préserve l'ordre relatif des éléments égaux.