7.0 KiB
La Flamme - Algorithmes de tri
La Flamme est une série Canal+ parodiant les émissions de téléréalité sentimentale de type Bachelor.
Contexte
Marc, le Bachelor de La Flamme, arrive à la Grande Cérémonie des Roses Finale.
Il a rencontré douze prétendant·e·s au fil des épisodes, et son équipe de production a calculé un score de compatibilité pour chacun·e.
Le problème : la liste est dans le désordre, et Marc doit la parcourir classée du moins compatible au plus compatible pour ménager le suspense et remettre la rose en dernier au ou à la grand·e vainqueur·e.
La production lui propose deux stratégies. À vous de les implémenter et de les comparer.
Les données
Le score de compatibilité est calculé selon la formule :
score = charme + sincérité - drama + karaoké + cuisine
Marc aime le charme, la sincérité, le talent au karaoké et la cuisine maison.
En revanche, chaque point de drama retire un point au score.
pretendants = [
{"nom": "Nadjim", "charme": 9, "sincerite": 5, "drama": 8, "karaoké": 7, "cuisine": 6, "score": 19},
{"nom": "Bibou", "charme": 6, "sincerite": 9, "drama": 2, "karaoké": 5, "cuisine": 8, "score": 26},
{"nom": "Sébastien", "charme": 8, "sincerite": 7, "drama": 3, "karaoké": 9, "cuisine": 4, "score": 25},
{"nom": "Valérie", "charme": 7, "sincerite": 8, "drama": 1, "karaoké": 6, "cuisine": 9, "score": 29},
{"nom": "Kevin", "charme": 5, "sincerite": 6, "drama": 9, "karaoké": 4, "cuisine": 3, "score": 9},
{"nom": "Stéphanie", "charme": 9, "sincerite": 4, "drama": 7, "karaoké": 8, "cuisine": 5, "score": 19},
{"nom": "Martial", "charme": 4, "sincerite":10, "drama": 1, "karaoké": 3, "cuisine": 7, "score": 23},
{"nom": "Chrystel", "charme": 8, "sincerite": 3, "drama": 6, "karaoké": 9, "cuisine": 6, "score": 20},
{"nom": "Didier", "charme": 6, "sincerite": 7, "drama": 4, "karaoké": 5, "cuisine":10, "score": 24},
{"nom": "Sandrine", "charme":10, "sincerite": 6, "drama": 5, "karaoké": 7, "cuisine": 4, "score": 22},
{"nom": "Jérémy", "charme": 3, "sincerite": 9, "drama": 2, "karaoké": 6, "cuisine": 8, "score": 24},
{"nom": "Natacha", "charme": 7, "sincerite": 5, "drama": 8, "karaoké":10, "cuisine": 5, "score": 19},
]
- Vérifier sur deux ou trois prétendant·e·s que la formule donne bien le score indiqué.
Partie 1 - Tri par sélection (rappel de Première)
La première stratégie de la production s'appelle "La Rose du Moins Aimé" :
"À chaque cérémonie, on parcourt tous les prétendant·e·s encore classé·e·s, on identifie celui ou celle qui a le score le plus bas, et on le ou la place en premier. On recommence jusqu'à avoir tout classé."
-
En une phrase, expliquer en quoi cette description correspond au tri par sélection.
-
Compléter la fonction suivante :
def tri_selection(tab):
n = len(tab)
for i in range(n):
idx_min = i
for j in range(i + 1, n):
if tab[j]["score"] < tab[idx_min]["score"]:
# à compléter
pass
# à compléter : echanger tab[i] et tab[idx_min]
return tab
-
Appliquer
tri_selectionà la listepretendantset afficher les noms dans l'ordre obtenu. -
Pour une liste de n prétendant·e·s, combien de comparaisons de scores effectue cet algorithme au total ? Exprimer le résultat en fonction de n, puis calculer pour n = 12.
Partie 2 - Tri fusion (diviser pour régner)
La deuxième stratégie de la production s'appelle "Les Deux Villas" :
"On sépare les prétendant·e·s en deux groupes. On classe chaque groupe séparément. Puis on réunit les deux listes classées en une seule, en les fusionnant."
C'est exactement l'algorithme de tri fusion, vu dans le cours.
2.1 - La fonction fusionner
def fusionner(gauche, droite):
resultat = []
i, j = 0, 0
while i < len(gauche) and j < len(droite):
if gauche[i]["score"] <= droite[j]["score"]:
resultat.append(gauche[i])
i += 1
else:
resultat.append(droite[j])
j += 1
return resultat + gauche[i:] + droite[j:]
- Expliquer le rôle des variables
ietjdans cette fonction. - Que se passe-t-il à la ligne
return resultat + gauche[i:] + droite[j:]?
Pourquoi est-il nécessaire d'ajoutergauche[i:]etdroite[j:]à la fin ? - Appliquer à la main
fusionnersur ces deux sous-listes déjà triées, et écrire le résultat étape par étape :
gauche = [{"nom": "Kevin", "score": 9}, {"nom": "Martial", "score": 23}]
droite = [{"nom": "Chrystel", "score": 20}, {"nom": "Valérie", "score": 29}]
2.2 - La fonction tri_fusion
def tri_fusion(tab):
if len(tab) <= 1:
return tab
milieu = len(tab) // 2
gauche = tri_fusion( ) # à compléter
droite = tri_fusion( ) # à compléter
return fusionner(gauche, droite)
- Compléter la fonction
tri_fusion. - Quel est le cas de base de cette fonction récursive ? Pourquoi une liste de taille 0 ou 1 est-elle "déjà triée" ?
- Appliquer
tri_fusionà la listepretendants. Vérifier que le résultat est identique à celui du tri par sélection.
2.3 - Déroulé de l'algorithme
- Sur la sous-liste ci-dessous, montrer toutes les étapes de
tri_fusion: les divisions successives, puis les fusions, jusqu'au résultat final.
sous_liste = [
{"nom": "Sandrine", "score": 22},
{"nom": "Kevin", "score": 9},
{"nom": "Bibou", "score": 26},
{"nom": "Chrystel", "score": 20},
]
Partie 3 - Comparaison des complexités
| Algorithme | Complexité |
|---|---|
| Tri par sélection | O(n²) |
| Tri fusion | O(n log n) |
-
Pour n = 12 prétendant·e·s :
- Combien d'opérations environ pour le tri par sélection ?
- Combien d'opérations environ pour le tri fusion ? (rappel : log₂(12) ≈ 3,58)
-
La saison 2 de La Flamme est un succès planétaire. Marc reçoit désormais 1 000 candidatures.
Calculer l'ordre de grandeur du nombre d'opérations pour chaque algorithme.
Que remarquez-vous ? -
La production doit choisir un algorithme à intégrer dans leur logiciel de classement. Lequel recommandez-vous, et pourquoi ?
Bonus - Marc change d'avis
Marc, dans un élan de narcissisme, décide finalement de classer les prétendant·e·s par charme décroissant plutôt que par score.
Modifier la fonction fusionner pour trier selon charme en ordre décroissant. Appliquer le tri fusion modifié à la liste et afficher le classement final.
Sources :
- Programme officiel NSI Terminale - Algorithmique
- La Flamme - Canal+
Auteur : Florian Mathieu - Licence CC BY-SA