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

# Définition de la fonction qui implémente l'algorithme de Tri par Sélection
def tri_selection(liste):
    # Parcourir tous les éléments de la liste
    for i in range(len(liste)):
        # Initialiser l'indice du minimum à la position actuelle
        min_index = i
        # Parcourir les éléments non triés
        for j in range(i+1, len(liste)):
            # Si l'élément actuel est inférieur à l'élément min actuel, mettre à jour min_index
            if liste[min_index] > liste[j]:
                min_index = j
        # Après avoir trouvé le minimum, échanger avec l'élément à la position i
        liste[i], liste[min_index] = liste[min_index], liste[i]
    # Retourner la liste triée
    return liste

# Liste des nombres qui doivent être triés
liste_a_trier = [64, 34, 25, 12, 22, 11, 90]

# Appeler la fonction tri_selection avec la liste à trier comme argument
liste_triee = tri_selection(liste_a_trier)

# Imprimer la liste triée pour vérifier le résultat
print("Liste triée :", liste_triee)

# Importe la bibliothèque de visualisation Matplotlib
import matplotlib.pyplot as plt  
import numpy as np  
# Importe des fonctions pour l'affichage interactif dans Jupyter
from IPython.display import display, clear_output  

import time  

# Définit la fonction de visualisation du Tri par Sélection
def visualiser_tri_selection(liste):
    n = len(liste)  # Détermine la longueur de la liste à trier
    fig, ax = plt.subplots()  # Crée une nouvelle figure et des axes pour le graphique
    rects = ax.bar(range(n), liste, color='skyblue')  # Dessine un diagramme en barres de la liste avec une couleur initiale
    ax.set_title('Tri par Sélection en Action')  # Définit le titre du graphique

    # Boucle principale du Tri par Sélection
    for i in range(n):
        min_idx = i  # Initialise l'indice du minimum à l'élément courant
        # Boucle pour trouver l'indice du minimum dans la sous-liste non triée
        for j in range(i+1, n):
            if liste[j] < liste[min_idx]:
                min_idx = j  # Met à jour l'indice du minimum si un élément plus petit est trouvé

        # Met à jour les couleurs des barres pour la visualisation
        for rect in rects:
            rect.set_color('skyblue')  # Réinitialise la couleur de toutes les barres
        rects[min_idx].set_color('red')  # Colore la barre du minimum actuel en rouge
        rects[i].set_color('yellow')  # Colore la barre à la position i en jaune

        # Échange le minimum trouvé avec l'élément à la position i
        liste[i], liste[min_idx] = liste[min_idx], liste[i]

        # Met à jour les hauteurs des barres pour refléter l'état actuel de la liste après l'échange
        for rect, h in zip(rects, liste):
            rect.set_height(h)  # Met à jour la hauteur de chaque barre

        clear_output(wait=True)  # Efface la sortie précédente pour éviter l'encombrement
        display(fig)  # Affiche le graphique mis à jour
        time.sleep(0.5)  # Introduit un délai pour rendre l'animation visible

    # Colore toutes les barres en vert une fois le tri terminé pour indiquer la liste complètement triée
    for rect in rects:
        rect.set_color('green')
    clear_output(wait=True)  # Efface la sortie précédente
    display(fig)  # Affiche le graphique final

# Crée une liste de nombres aléatoires à trier
liste_a_trier = np.random.randint(1, 100, 20)
visualiser_tri_selection(liste_a_trier)  # Appelle la fonction de visualisation avec la liste générée