Parmi les différentes méthodes de tri existantes, le Tri par Insertion se distingue par sa simplicité. Cette technique, qui imite la manière dont vous pourriez trier des cartes dans vos mains, consiste à prendre un élément de la liste et à l’insérer à sa position correcte parmi les éléments déjà triés. Ce processus est répété pour chaque élément jusqu’à ce que la liste entière soit ordonnée.
Implémentation du Tri par Insertion en Python
# Définition de la fonction de tri par insertion
def tri_insertion(liste):
# Parcourir chaque élément de la liste à partir du deuxième élément
for i in range(1, len(liste)):
# La clé est l'élément courant à insérer dans la partie triée de la liste
cle = liste[i]
# Commencer à comparer avec l'élément juste avant la clé
j = i-1
# Déplacer les éléments de liste[0..i-1] qui sont plus grands que la clé
# à une position en avant de leur position actuelle
while j >= 0 and cle < liste[j]:
liste[j + 1] = liste[j] # Déplacer l'élément vers la droite
j -= 1 # Passer à l'élément précédent dans la partie triée
# Insérer la clé à sa position correcte
liste[j + 1] = cle
# Retourner la liste triée
return liste
# Liste d'exemple à trier
liste_exemple = [22, 27, 16, 2, 18, 6]
# Afficher la liste avant le tri
print("Liste avant le tri:", liste_exemple)
# Appliquer le tri par insertion à la liste d'exemple
liste_triee = tri_insertion(liste_exemple)
# Afficher la liste après le tri
print("Liste après le tri:", liste_triee)
Explication du Code
- Initialisation de la Boucle : La boucle
forcommence à 1 car le premier élément est considéré comme déjà trié. - Sélection de la Clé : La variable
clecontient l’élément courant à insérer. On le compare ensuite aux éléments précédents pour trouver sa place correcte. - Trouver la Position Correcte : La boucle
whiledéplace les éléments plus grands quecled’une position vers la droite pour faire de la place pourcle. - Insertion : Après avoir trouvé la position correcte,
cleest insérée.
Visualisation du Tri par Insertion
Pour mieux comprendre le fonctionnement du Tri par Insertion avec Python, rien ne vaut une visualisation concrète de chaque étape de l’algorithme. Le code suivant utilise Matplotlib et numpy pour créer une animation dynamique qui illustre le processus de tri.
Ps : Il faut utiliser Jupyter Notebook pour la visualisation.
from IPython.display import display, clear_output
import matplotlib.pyplot as plt
import numpy as np
import time
def tri_insertion_visual_jupyter(liste):
fig, ax = plt.subplots()
n = len(liste)
for i in range(1, n):
cle = liste[i]
j = i-1
# Dessiner l'état actuel de la liste
ax.clear() # Effacer le contenu des axes pour le nouveau tracé
bars = ax.bar(range(n), liste, color='skyblue')
bars[i].set_color('red') # Mettre en évidence l'élément à déplacer en rouge
display(fig) # Afficher la figure dans la sortie de la cellule
# Déplacer l'élément à sa position correcte
while j >= 0 and cle < liste[j]:
liste[j + 1] = liste[j]
j -= 1
clear_output(wait=True)
ax.clear()
bars = ax.bar(range(n), liste, color='skyblue')
bars[j+1].set_color('red') # Continuer à mettre en évidence l'élément déplacé
display(fig)
time.sleep(0.5)
liste[j + 1] = cle
clear_output(wait=True)
ax.clear()
bars = ax.bar(range(n), liste, color='skyblue')
bars[j+1].set_color('green') # Montrer l'élément inséré en vert
display(fig)
time.sleep(0.5)
# Afficher l'état final
clear_output(wait=True)
ax.clear()
ax.bar(range(n), liste, color='lightgreen')
ax.set_title('État Final Après le Tri')
display(fig)
# Créer une liste de valeurs aléatoires
liste_a_trier = np.random.randint(1, 100, 15)
# Exécuter la fonction de visualisation
tri_insertion_visual_jupyter(liste_a_trier)
Dans script :
- À chaque itération de la boucle principale, l’élément à déplacer (
cle) est coloré en rouge (bars[i].set_color('red')) pour le mettre en évidence. - Pendant que cet élément est déplacé (
whileloop), il reste en rouge pour indiquer qu’il est l’élément actuellement examiné et potentiellement déplacé. - Une fois que
cleest insérée à sa position correcte, elle est colorée en vert (bars[j+1].set_color('green')) pour indiquer qu’elle a été correctement placée. clear_output(wait=True)etdisplay(fig)sont utilisés à chaque étape pour rafraîchir l’affichage et créer un effet d’animation fluide.- Une pause (
time.sleep(0.5)) est ajoutée pour ralentir l’animation, rendant les changements plus faciles à suivre.
Lire aussi :
Le Tri par Sélection avec Python
