Tris par Insertion en Python : Exercices Corrigés

Le tri par insertion est un algorithme de tri simple mais efficace qui consiste à trier un tableau en insérant chaque élément à sa place appropriée dans le sous-tableau trié. C’est une excellente occasion d’apprendre les bases de l’algorithme de tri et d’améliorer vos compétences en programmation Python. Dans cet article, nous allons explorer des exercices pratiques sur le tri par insertion en Python, avec des solutions et des explications.

Lire le cours : Tri par insertion python

Exercice 1 : Tri d’une Liste

Écrivez une fonction Python pour trier une liste d’entiers en utilisant l’algorithme de tri par insertion.

Solution :

def tri_insertion(liste):
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and cle < liste[j]:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle

# Exemple d'utilisation :
ma_liste = [12, 11, 13, 5, 6]
tri_insertion(ma_liste)
print("Liste triée :", ma_liste)

Dans cet exercice, nous utilisons l’algorithme de tri par insertion pour trier une liste d’entiers. La fonction tri_insertion parcourt la liste, insérant chaque élément à sa place correcte dans le sous-tableau trié à gauche.

Exercice 2 : Tri Descendant

Modifiez la fonction précédente pour trier la liste dans l’ordre décroissant.

Solution :

def tri_insertion_descendant(liste):
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and cle > liste[j]:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle

# Exemple d'utilisation :
ma_liste = [12, 11, 13, 5, 6]
tri_insertion_descendant(ma_liste)
print("Liste triée en ordre décroissant :", ma_liste)

Ici, nous avons ajusté la condition de la boucle interne pour trier dans l’ordre décroissant en inversant les comparaisons.

Exercice 3 : Tri par Insertion Récursif

Écrivez une fonction récursive pour trier une liste d’entiers en utilisant le tri par insertion.

Solution :

def tri_insertion_recursif(liste, n):
    if n <= 1:
        return
    tri_insertion_recursif(liste, n-1)
    cle = liste[n-1]
    j = n - 2
    while j >= 0 and cle < liste[j]:
        liste[j + 1] = liste[j]
        j -= 1
    liste[j + 1] = cle

# Exemple d'utilisation :
ma_liste = [12, 11, 13, 5, 6]
tri_insertion_recursif(ma_liste, len(ma_liste))
print("Liste triée (version récursive) :", ma_liste)

Dans cet exercice, nous utilisons la récursivité pour trier la liste. La fonction tri_insertion_recursif trie les n-1 premiers éléments de la liste, puis insère le n-ème élément à sa place correcte.

Exercice 4 : Tri par Insertion d’une Liste d’Objets

Modifiez la fonction de tri par insertion pour trier une liste d’objets personnalisés en fonction d’un attribut spécifique de ces objets.

Solution :

Supposons que nous ayons une classe Personne avec des attributs nom et age, et que nous voulions trier une liste de personnes par âge.

class Personne:
    def __init__(self, nom, age):
        self.nom = nom
        self.age = age

def tri_insertion_personnes(liste):
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and cle.age < liste[j].age:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle

# Exemple d'utilisation :
personnes = [Personne("Alice", 25), Personne("Bob", 20), Personne("Charlie", 30)]
tri_insertion_personnes(personnes)
for personne in personnes:
    print(f"{personne.nom} ({personne.age} ans)")

Ici, nous avons défini une classe Personne et adapté la fonction de tri par insertion pour trier une liste d’objets Personne en fonction de leur attribut age.

Bien sûr, voici la deuxième partie des exercices avancés sur le tri par insertion en Python :

Exercice 5 : Tri par Insertion avec Comptage d’Opérations

Écrivez une fonction qui trie une liste d’entiers en utilisant le tri par insertion et comptez le nombre total d’opérations (comparaisons et déplacements) effectuées pendant le tri.

Solution :

def tri_insertion_comptage(liste):
    operations = 0  # Compteur d'opérations
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and cle < liste[j]:
            liste[j + 1] = liste[j]
            j -= 1
            operations += 1  # Incrémente le compteur d'opérations
        liste[j + 1] = cle
    return operations

# Exemple d'utilisation :
ma_liste = [12, 11, 13, 5, 6]
operations = tri_insertion_comptage(ma_liste)
print("Liste triée avec", operations, "opérations.")

Dans cet exercice, nous avons ajouté un compteur pour suivre le nombre total d’opérations (comparaisons et déplacements) effectuées pendant le tri.

Exercice 6 : Tri par Insertion avec Temps d’Exécution

Modifiez la fonction de tri par insertion pour mesurer le temps d’exécution nécessaire pour trier une grande liste d’entiers.

Solution :

import random
import time

def tri_insertion_temps(liste):
    debut = time.time()
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and cle < liste[j]:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle
    temps_execution = time.time() - debut
    return temps_execution

# Génération d'une grande liste aléatoire
ma_liste = [random.randint(1, 10000) for _ in range(10000)]

temps = tri_insertion_temps(ma_liste)
print("Temps d'exécution du tri :", temps, "secondes")

Dans cet exercice, nous mesurons le temps d’exécution nécessaire pour trier une grande liste d’entiers générée aléatoirement.

Exercice 7 : Tri par Insertion Descendant avec Fonction de Comparaison Personnalisée

Écrivez une fonction qui trie une liste d’objets personnalisés en utilisant le tri par insertion, avec la possibilité de spécifier une fonction de comparaison personnalisée.

Solution :

Supposons que nous ayons une classe Produit avec des attributs nom et prix, et que nous voulions trier une liste de produits par prix.

class Produit:
    def __init__(self, nom, prix):
        self.nom = nom
        self.prix = prix

# Fonction de comparaison personnalisée par prix
def comparer_prix(produit):
    return produit.prix

def tri_insertion_personnalise(liste, fonction_comparaison):
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and fonction_comparaison(cle) < fonction_comparaison(liste[j]):
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle

# Exemple d'utilisation :
produits = [Produit("Livre", 15), Produit("Ordinateur", 1200), Produit("Stylo", 1)]
tri_insertion_personnalise(produits, comparer_prix)
for produit in produits:
    print(f"{produit.nom} (${produit.prix})")

Dans cet exercice, nous utilisons une fonction de comparaison personnalisée pour trier une liste d’objets Produit par prix.

Ces exercices avancés vous permettront d’approfondir vos compétences en tri par insertion en Python et de les appliquer à des scénarios plus complexes. Continuez à explorer et à pratiquer pour devenir un expert en algorithmes de tri.

Conclusion

Le tri par insertion est un algorithme de tri simple mais puissant en Python. En pratiquant ces exercices, vous avez acquis une compréhension plus profonde de cet algorithme et de son application à des problèmes variés. Le tri par insertion est un excellent moyen de renforcer vos compétences en programmation et de comprendre les bases de l’algorithme de tri. N’hésitez pas à explorer davantage et à appliquer ces connaissances à des projets plus complexes.