Trier un million de notes
Un algorithme de tri range les éléments d’une liste du plus petit au plus grand. Le tri par sélection, le tri par insertion et le tri par fusion font le même travail avec des coûts très différents.
Une université trie un million de notes. Avec un tri simple, il faut environ 500 milliards de comparaisons. Avec le tri par fusion, vingt millions suffisent.
À la fin de cette leçon
Remarque
Je peux dérouler le tri par insertion, par sélection et par fusion sur une petite liste.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Tri | ranger une liste dans l’ordre croissant |
| Tri par sélection | chercher le plus petit et le ranger devant |
| Tri par insertion | glisser chaque valeur à sa place dans la partie déjà triée |
| Tri par fusion | couper en deux, trier chaque moitié, puis les fusionner |
| Comparaison | un test entre deux valeurs, qui compte pour une étape |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La sélection range le plus petit devant
À chaque tour, le tri par sélection cherche le plus petit élément de la partie non triée. Il l’échange avec le premier élément de cette partie.
Après chaque tour, une valeur de plus est à sa place définitive. Il faut n − 1 tours pour une liste de n valeurs.
Exemple travaillé : sélection sur 5 notes
| Tour | Plus petit trouvé | Liste après l’échange |
|---|---|---|
| 1 | 10 | [10, 29, 14, 37, 13] |
| 2 | 13 | [10, 13, 14, 37, 29] |
| 3 | 14 (déjà en place) | [10, 13, 14, 37, 29] |
| 4 | 29 | [10, 13, 14, 29, 37] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le tri par sélection qui compte
# Tri par sélection : on cherche le plus petit, on le range devant.
l = [29, 10, 14, 37, 13]
comparaisons = 0
for i in range(len(l)):
m = i
for j in range(i + 1, len(l)):
comparaisons = comparaisons + 1
if l[j] < l[m]:
m = j
temp = l[i]
l[i] = l[m]
l[m] = temp
print(l, "comparaisons :", comparaisons)
# Essayez avec une liste déjà triée : le compte change-t-il ?
L’insertion glisse chaque valeur à sa place
Le tri par insertion garde au début de la liste une partie déjà triée. Il prend la valeur suivante et la fait glisser vers la gauche, en décalant les plus grandes.
C’est le geste de quelqu’un qui range ses cartes à jouer. Si la liste est déjà presque triée, chaque valeur glisse très peu.
Exemple travaillé : insertion sur 5 notes
| Valeur prise | Partie triée avant | Partie triée après |
|---|---|---|
| 10 | [29] | [10, 29] |
| 14 | [10, 29] | [10, 14, 29] |
| 37 | [10, 14, 29] | [10, 14, 29, 37] |
| 13 | [10, 14, 29, 37] | [10, 13, 14, 29, 37] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le tri par insertion qui compte
# Tri par insertion : on glisse chaque valeur à sa place.
l = [29, 10, 14, 37, 13]
comparaisons = 0
for i in range(1, len(l)):
valeur = l[i]
j = i - 1
while j >= 0:
comparaisons = comparaisons + 1
if l[j] > valeur:
l[j + 1] = l[j] # on décale vers la droite
j = j - 1
else:
break
l[j + 1] = valeur
print(l, "comparaisons :", comparaisons)
# Remplacez la liste par [10, 13, 14, 29, 37] : le compte tombe à 4.
La fusion coupe en deux puis fusionne
Le tri par fusion coupe la liste en deux moitiés et trie chaque moitié de la même façon. Une liste d’un seul élément est déjà triée.
On fusionne ensuite deux listes triées : on regarde les deux premiers éléments, on prend le plus petit, et on recommence. Le devoir de cette leçon écrit cette fusion.
Exemple travaillé : fusion sur 5 notes
| Étape | Listes en cours |
|---|---|
| Couper | [29, 10, 14, 37, 13] |
| Couper encore | [29, 10] et [14, 37, 13] |
| Jusqu’à un seul élément | [29] [10] [14] [37] [13] |
| Fusionner deux à deux | [10, 29] et [14] et [13, 37] |
| Fusionner encore | [10, 29] et [13, 14, 37] |
| Fusion finale | [10, 13, 14, 29, 37] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le coût des trois tris
| Tri | Pour 1 000 valeurs | Pour 1 000 000 de valeurs | Complexité |
|---|---|---|---|
| Sélection | 499 500 comparaisons, toujours | environ 500 milliards | O(n²) |
| Insertion | de 999 à 499 500 | de 1 million à 500 milliards | O(n²), O(n) si presque triée |
| Fusion | environ 10 000 | environ 20 millions | O(n log n) |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Trier des nombres avec le système
printf '29\n10\n14\n37\n13\n' | sort -n | xargsAffiché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.
Compter les comparaisons de la sélection
python3 -c "exec('l = [29, 10, 14, 37, 13]\nc = 0\nfor i in range(len(l)):\n m = i\n for j in range(i + 1, len(l)):\n c = c + 1\n if l[j] < l[m]:\n m = j\n temp = l[i]\n l[i] = l[m]\n l[m] = temp\nprint(l, c)')"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.
Compter les comparaisons de l’insertion
python3 -c "exec('l = [29, 10, 14, 37, 13]\nc = 0\nfor i in range(1, len(l)):\n v = l[i]\n j = i - 1\n while j >= 0:\n c = c + 1\n if l[j] > v:\n l[j + 1] = l[j]\n j = j - 1\n else:\n break\n l[j + 1] = v\nprint(l, c)')"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.
Erreur fréquente
Attention
Beaucoup pensent que le tri par fusion est toujours le meilleur. Pour une liste presque triée, l’insertion fait environ n étapes, bien moins. Le tri par fusion demande aussi une liste de plus en mémoire. Choisissez le tri d’après les données que vous avez.