Visualiser des algorithmes de tri avec Matplotlib

Pourquoi visualiser les algorithmes de tri ?

Tu as déjà appris les algorithmes de tri en NSI, comme le tri à bulles ou le tri par insertion. Tu connais peut-être même leur complexité algorithmique par cœur. Mais les as-tu vraiment vus travailler ? Comprendre un algorithme, c'est une chose. Voir les données se réorganiser en temps réel, c'est une révélation ! La visualisation te permet de :

• Comprendre intuitivement la logique de l'algorithme.
• Comparer l'efficacité de différents tris en voyant lequel est le plus rapide.
• Déboguer ton code en identifiant visuellement où une opération échoue.
• Rendre ton apprentissage bien plus concret et engageant.

Dans ce projet, nous allons utiliser Matplotlib, la bibliothèque de référence pour la visualisation de données en Python, et plus précisément son module d'animation, pour donner vie à ces algorithmes.

Mettre en place son environnement de travail

Avant de coder, assure-toi d'avoir les bons outils. Pour ce projet, tu auras besoin de :

• Python 3.7 ou supérieur installé sur ta machine.
• Les bibliothèques Matplotlib et NumPy.

Tu peux les installer facilement via pip dans ton terminal :

pip install matplotlib numpy

Nous allons structurer notre code en deux parties principales :

1. L'algorithme de tri lui-même, que nous modifierons légèrement pour qu'il "signale" chaque étape importante.
2. La fonction d'animation de Matplotlib qui va capturer ces signaux et les dessiner.

Créer un générateur d'étapes

La clé de la visualisation est de ne pas trier la liste d'un coup, mais de rendre compte de chaque changement. Pour cela, nous transformons notre fonction de tri en un générateur (avec le mot-clé yield). À chaque fois que deux éléments sont comparés ou échangés, le générateur renvoie (yield) un instantané de la liste.

Voici un exemple pour le tri à bulles :

def tri_a_bulles_etapes(data):
n = len(data)
for i in range(n):
for j in range(0, n-i-1):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
yield data.copy() # On renvoie une COPIE de l'état actuel

Animer le tri à bulles avec Matplotlib

Maintenant, passons à la partie graphique. Nous allons créer une animation où chaque barre représente un nombre, et sa hauteur correspond à sa valeur.

Voici le code complet pour animer notre tri à bulles :

import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np

# 1. Préparer les données et le générateur
data = np.random.permutation(50) # Liste mélangée de 0 à 49
generateur_etapes = tri_a_bulles_etapes(data.tolist())

# 2. Initialiser la figure
fig, ax = plt.subplots(figsize=(10,6))
ax.set_title("Animation du Tri à Bulles")
bars = ax.bar(range(len(data)), data, color='skyblue')

# 3. Fonction de mise à jour pour l'animation
def update(frame):
# 'frame' est l'état de la liste renvoyé par le générateur
for bar, hauteur in zip(bars, frame):
bar.set_height(hauteur)
return bars

# 4. Créer l'animation
ani = animation.FuncAnimation(fig, update, frames=generateur_etapes,
interval=50, repeat=False, save_count=1500)

plt.show()

Explications : FuncAnimation appelle la fonction update pour chaque "frame" (image) que produit notre générateur. L'argument interval=50 contrôle la vitesse (50 millisecondes entre les images). Lance ce code, et tu verras les barres "danser" jusqu'à être parfaitement ordonnées !

Aller plus loin : comparer plusieurs algorithmes

Le vrai pouvoir de la visualisation apparaît quand on compare. Tu peux facilement adapter le code pour le tri par insertion ou le tri par sélection.

Exemple avec le Tri par Insertion

Modifie simplement le générateur :

def tri_insertion_etapes(data):
for i in range(1, len(data)):
cle = data[i]
j = i-1
while j >= 0 and cle < data[j]:
data[j+1] = data[j]
j -= 1
yield data.copy()
data[j+1] = cle
yield data.copy()

En créant deux figures côte à côte, tu peux lancer les deux animations simultanément. Tu verras clairement que le tri par insertion est souvent plus efficace (moins d'échanges) que le tri à bulles sur des données partiellement triées.

Projet final : créer une application interactive

Pour peaufiner ton projet NSI, tu peux en faire une petite application avec des contrôles. Utilise matplotlib.widgets pour ajouter :

• Un bouton de démarrage/pause.
• Un menu déroulant pour choisir l'algorithme (bulles, insertion, sélection).
• Un curseur pour ajuster la vitesse de l'animation.
• Un bouton "Mélanger" pour générer un nouveau tableau aléatoire.

Cela montrera que tu maîtrises non seulement les algorithmes, mais aussi la création d'interfaces utilisateur simples pour présenter ton travail. C'est exactement le genre de projet qui impressionne lors du Grand Oral !

N'oublie pas de bien commenter ton code et d'expliquer tes choix dans un petit rapport. Bonne visualisation !