Classer les scores d’un jeu vidéo
Un tri range les éléments d’une liste dans un ordre, par exemple du plus petit au plus grand. Les classements de jeux, les playlists et les listes de prix en ont besoin.
Il existe plusieurs méthodes. Elles donnent le même résultat, mais ne travaillent pas de la même façon.
À la fin de cette leçon
Remarque
Je peux trier une liste avec le tri à bulles, le tri par insertion et le tri fusion.
Mots clés
| Mot | Ce que ça veut dire |
|---|---|
| Tri | ranger les éléments dans un ordre |
| Échange | deux éléments voisins changent de place |
| Tri à bulles | on échange deux voisins mal rangés, passe après passe |
| Tri par insertion | on glisse chaque élément à sa place parmi ceux déjà triés |
| Tri fusion | on coupe la liste, puis on fusionne des morceaux triés |
| Fusionner | réunir deux listes triées en une seule liste triée |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le tri à bulles échange les voisins
On parcourt la liste. Chaque fois que deux voisins sont mal rangés, on les échange. Une passe est un parcours complet.
Après la première passe, le plus grand élément est tout à droite. On recommence avec une case de moins, jusqu’à ce que tout soit rangé.
Exemple travaillé : trier 5, 2, 9, 1
| Passe | Liste après la passe | Échanges dans la passe |
|---|---|---|
| Départ | 5, 2, 9, 1 | 0 |
| 1 | 2, 5, 1, 9 | 2 |
| 2 | 2, 1, 5, 9 | 1 |
| 3 | 1, 2, 5, 9 | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lance le tri à bulles, compte les échanges
def tri_a_bulles(liste):
echanges = 0
for passe in range(len(liste) - 1):
for i in range(len(liste) - 1 - passe):
if liste[i] > liste[i + 1]:
temporaire = liste[i]
liste[i] = liste[i + 1]
liste[i + 1] = temporaire
echanges = echanges + 1
print("échanges :", echanges)
scores = [5, 2, 9, 1]
tri_a_bulles(scores)
print(scores)
# Essaie avec [1, 2, 3, 4] : combien d’échanges ?
Le tri par insertion range comme des cartes
Tu tiens des cartes dans la main. Tu prends la carte suivante et tu la glisses à sa place parmi les cartes déjà rangées.
Le tri par insertion fait pareil. La partie gauche de la liste est toujours triée. On décale les plus grands vers la droite, puis on pose la valeur dans le trou.
Lance le tri par insertion
def tri_par_insertion(liste):
for i in range(1, len(liste)):
valeur = liste[i]
place = i - 1
# On décale vers la droite tout ce qui est plus grand.
while place >= 0 and liste[place] > valeur:
liste[place + 1] = liste[place]
place = place - 1
liste[place + 1] = valeur
return liste
print(tri_par_insertion([5, 2, 9, 1, 7]))
# Essaie une liste avec deux valeurs égales.
Fusionner deux listes triées
Le tri fusion repose sur une idée : réunir deux listes déjà triées est facile. On compare leurs deux premiers éléments et on prend le plus petit.
On recommence jusqu’à vider une liste, puis on recopie le reste de l’autre.
Lance la fusion de deux listes triées
def fusionner(a, b):
resultat = []
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
resultat.append(a[i])
i = i + 1
else:
resultat.append(b[j])
j = j + 1
while i < len(a):
resultat.append(a[i])
i = i + 1
while j < len(b):
resultat.append(b[j])
j = j + 1
return resultat
print(fusionner([2, 5, 9], [1, 6, 7, 10]))
Le tri fusion part de morceaux d’un élément
Une liste d’un seul élément est déjà triée. On part donc de morceaux d’un élément, puis on fusionne les morceaux deux par deux.
On répète jusqu’à n’avoir plus qu’un morceau : la liste triée. Il existe aussi une version récursive, que tu verras à la leçon 5.
Voici le tri fusion complet
def tri_fusion(liste):
morceaux = []
for valeur in liste:
morceaux.append([valeur])
while len(morceaux) > 1:
suivants = []
i = 0
while i < len(morceaux):
if i + 1 < len(morceaux):
suivants.append(fusionner(morceaux[i], morceaux[i + 1]))
else:
suivants.append(morceaux[i])
i = i + 2
morceaux = suivants
if len(morceaux) == 0:
return []
return morceaux[0]
print(tri_fusion([5, 2, 9, 1, 7, 3]))
# Copie fusionner du bloc précédent au-dessus, puis lance.
Une erreur fréquente
Attention
Beaucoup pensent que fusionner trie n’importe quelles deux listes. Elle suppose que chaque liste est déjà triée. Si ce n’est pas le cas, le résultat est dans un ordre quelconque. Trie d’abord les petits morceaux.
Compte les échanges pour trier huit jours
docker exec jupyter python3 -c "import csv; v = [int(x['hires']) for x in csv.DictReader(open('hires.csv'))]; w = v[:8]; print(w, sum(1 for i in range(8) for j in range(i + 1, 8) if w[i] > w[j]))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Trouve les extrêmes et la valeur du milieu
docker exec jupyter python3 -c "import csv; v = [int(x['hires']) for x in csv.DictReader(open('hires.csv'))]; print(sorted(v, reverse=True)[:3], sorted(v)[:3], sorted(v)[182])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que disent les deux Runs
Le premier Run prend les huit premiers jours de locations de vélos. Il affiche la liste, puis 11 : le nombre d’échanges que ferait le tri à bulles pour la ranger.
Le second Run trie les 365 jours. Il affiche les trois plus gros jours, les trois plus petits, et la valeur du milieu de la liste triée, 273.
Pour aller plus loin : compter les échanges
Ajoute un compteur de comparaisons au tri par insertion. Lance-le sur [1, 2, 3, 4, 5, 6], puis sur [6, 5, 4, 3, 2, 1].
Dans quel cas travaille-t-il le moins ? Écris une phrase pour expliquer pourquoi.