Le Tri à Bulles avec Python : Guide Étape par Étape

Le Tri à Bulles, souvent considéré comme l’un des algorithmes de tri les plus simples, est un incontournable pour ceux qui débutent en programmation, notamment en Python. Dans cette section, nous explorerons le fonctionnement de base de cet algorithme, en mettant en lumière ses avantages et inconvénients, essentiels pour comprendre quand et comment l’utiliser efficacement.

Implémentation du Tri à Bulles en Python

Le Tri à Bulles en Python peut être implémenté de manière concise. Voici un exemple de base :

def tri_bulles(liste):
    n = len(liste)
    for i in range(n):
        for j in range(0, n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
    return liste

Ce code représente l’algorithme de Tri à Bulles, où nous effectuons des passages répétés sur la liste pour effectuer les comparaisons et les échanges nécessaires.

Explication Détaillée du Code

• La fonction tri_bulles prend en paramètre une liste à trier.
• n = len(liste) détermine la longueur de la liste, qui sera utilisée pour contrôler le nombre de passages.
• La première boucle for représente le nombre de passages à travers la liste.
• La seconde boucle for permet de comparer les éléments adjacents. n-i-1 est utilisé pour réduire la portée de la comparaison à chaque passage, car les éléments à la fin de la liste sont déjà triés.
• La condition if liste[j] > liste[j+1]: vérifie si les éléments adjacents sont dans le mauvais ordre et les échange le cas échéant avec liste[j], liste[j+1] = liste[j+1], liste[j].

Exemples de Listes à Trier et Résultats Attendus

Prenons quelques exemples pour illustrer l’efficacité de notre fonction :

print(tri_bulles([34, 10, 64, 51, 32, 21]))
print(tri_bulles([5, 3, 8, 6, 7, 2]))

[10, 21, 32, 34, 51, 64]
[2, 3, 5, 6, 7, 8]

Visualisation du Tri à Bulles

Ici, nous allons voir une méthode pour visualiser le fonctionnement de l’algorithme du Tri à Bulles en Python. L’objectif est de rendre l’algorithme plus compréhensible et interactif. Pour cela, nous utiliserons les bibliothèques matplotlib et numpy pour créer des graphiques qui montrent comment les éléments de la liste sont comparés et échangés au fil du temps (pour une meilleure visualisation, utilisez Jupyter NoteBook).

import matplotlib.pyplot as plt
import numpy as np

def visualiser_tri_bulles(liste):
    n = len(liste)
    
    for i in range(n):
        already_sorted = True
        for j in range(0, n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
                already_sorted = False

            # Mise à jour du graphique à chaque comparaison
            plt.clf()  # Efface le graphique actuel
            plt.bar(range(len(liste)), liste, color='lightblue')
            plt.bar(j, liste[j], color='red')  # Élément actuellement examiné
            plt.bar(j + 1, liste[j + 1], color='red')  # Élément adjacent
            plt.title("Tri à Bulles en Action - Étape {}".format(i*n+j))
            plt.xlabel("Index")
            plt.ylabel("Valeur")
            plt.pause(0.1)

        # Sortie anticipée si la liste est déjà triée
        if already_sorted:
            break

    plt.show()

# Test de la fonction
liste_à_trier = np.random.randint(1, 100, 10)
visualiser_tri_bulles(liste_à_trier)

Dans le code ci-dessus :

• La liste est parcourue et les éléments sont comparés et échangés si nécessaire.
• À chaque comparaison, le graphique est effacé (plt.clf()) puis redessiné avec les éléments actuels.
• Les éléments en cours de comparaison sont colorés en rouge pour les distinguer.
• Une pause (plt.pause(0.1)) est utilisée pour ralentir la génération des graphes.
• Si aucun échange n’est effectué pendant une itération complète (indiquant que la liste est triée), la boucle se termine prématurément pour améliorer l’efficacité.

Lire aussi :

Le Tri par Sélection : Implémentation et Visualisation avec Python

Tri par Insertion avec Python