1.8 KiB
08 — La Course des Algorithmes
Algorithmes : Tri par insertion vs Tri par sélection (comparaison) Difficulté : Difficile Durée estimée : 1h15 — 1h30
Contexte
On sait que les deux tris ont une complexité quadratique (O(n²)) dans le pire des cas. Mais en pratique, se comportent-ils vraiment pareil ? C'est ce que vous allez mesurer.
Vous allez tester les deux algorithmes sur différentes tailles de listes et dans différentes configurations, afficher les résultats et tirer des conclusions.
Étapes
Étape 1 — Copier les deux tris
Recopiez dans le starter vos fonctions tri_insertion(tab) et tri_selection(tab) qui fonctionnent sur des listes d'entiers.
Étape 2 — Mesurer le temps
La fonction mesurer_temps(fonction, tab) est déjà fournie. Elle prend une copie de la liste pour ne pas la modifier et mesure le temps en millisecondes.
Important
: toujours travailler sur une copie (
tab[:]) pour que les deux algos partent du même état.
Étape 3 — Tester sur différentes tailles
Testez pour n ∈ [100, 500, 1000, 2000, 5000] avec une liste aléatoire. Affichez un tableau comparatif.
Étape 4 — Tester les cas particuliers
Pour n = 1000, testez :
- Liste aléatoire
- Liste déjà triée (croissant)
- Liste triée à l'envers (décroissant)
Affichez les résultats. Quel algorithme est avantagé selon le cas ?
Étape 5 — Tracer un graphique (extension)
Si vous connaissez matplotlib, tracez les courbes de temps en fonction de n pour les deux algorithmes.
import matplotlib.pyplot as plt
Ce que vous devez rendre
- Le programme avec le tableau comparatif
- Une conclusion écrite : dans quels cas préférez-vous le tri par insertion ? Le tri par sélection ? Justifiez avec vos mesures.