50 lines
1.8 KiB
Markdown
50 lines
1.8 KiB
Markdown
|
# 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.
|
||
|
|
|
||
|
|
```python
|
||
|
|
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.
|