Tri par insertion
Nous avons vu que la recherche dichotomique nécessite de travailler sur un tableau de données triées.
Nous avons utilisé la méthode sort ou la fonction native sorted de Python.
Cette fonction trie le tableau. Ok.
Nous allons voir aujourd'hui une méthode de tri, le TRI PAR INSERTION.
Mais comment ça fonctionne ?
Logiciel nécessaire pour l'activité : Python 3 : Spyder, IDLE ou le site repl.it ...
Prérequis : les activités suivantes
- Algorithme : parcours séquentiel d'un tableau,
A RENDRE ✎ : questions 08-13-14-15
1 - Tri par insertion de cartes par un humain
Le principe du tri par insertion est l'une des méthodes de tri les plus naturelles mais pas la plus efficace.
Le principe est simple : on tri le tableau au fur et à mesure en rajoutant un élément à la fois et en le plaçant au bon endroit dans le tableau temporaire.
C'est ce qu'on fait lorsqu'on trie nos cartes à jouer.
Imaginons qu'on veuille trier les cartes suivantes de la plus petite à la plus grande.
On voit que les cartes sont dans le bon ordre du 2 au 9. C'est le 4 qui pose problème.
Spontanément, on va laisser le 2 en place mais on va décaler le 8 et le 9.
Et voilà : il ne reste plus qu'à mettre le 4 entre le 2 et le 8.
Mais vous avez un gros avantage sur l'ordinateur : vous avez un cerveau. Ici, il va falloir détailler ce qu'on réalise. Notamment, difficile de placer un élément entre l'index 0 et l'index 1 d'un tableau !
La méthode que nous allons expliquer réalise donc ceci :
- Mettre en mémoire le 4.
- Décaler les cartes supérieures à 4 d'une case à droite dans le tableau en augmentant leur index de 1
- Mettre le 4 à l'index devenu libre
2 - Principe du tri par insertion dans un tableau
Imaginons que vous ayez à trier ce tableau de nombres entiers [90, 60, 20, 50, 80].
Etape initiale
Nous allons commencer par travailler sur un tableau (en bleu) ne contenant qu'un seul élément, comme ça il sera trié au moins !
| ↓ | |||||
| Elément | 90 | 60 | 20 | 50 | 80 |
Etape 2 : on rajoute l'élément suivant
On rajoute 60 dans le sous-tableau bleu.
| ↓ | |||||
| Elément | 90 | 60 | 20 | 50 | 80 |
Mettons la clé 60 en mémoire.
| ↓ | |||||
| Elément | 90 | 60 | 20 | 50 | 80 |
| 60 |
Ensuite, on décale d'une case à droite l'éléments à gauche de la clé s'il est supérieur à la clé.
On compare 90 à la clé 60 : on décale 90 d'une case à droite car 90 est plus grand que la clé.
| ↓ | ↓ | ||||
| Elément | 90 | 90 | 20 | 50 | 80 |
| 60 |
On remarquera qu'on a donc écrasé la valeur 60 qui était présente sur l'index 1.
Il n'y a plus d'autres valeurs à surveiller. On place alors la clé sur l'index 0.
| Elément | 60 | 90 | 20 | 50 | 80 |
Nous avons maintenant un sous-tableau de deux éléments triés.
Etape suivante : on rajoute l'élément suivant
On rajoute 20 dans le sous-tableau.
| ↓ | |||||
| Elément | 60 | 90 | 20 | 50 | 80 |
Mettons la clé 20 en mémoire.
| ↓ | |||||
| Elément | 60 | 90 | 20 | 50 | 80 |
| 20 |
On compare d'abord 90 à la clé 20 : on décale 90 d'une case à droite car 90 est plus grand que la clé.
| ↓ | ↓ | ||||
| Elément | 60 | 90 | 90 | 50 | 80 |
| 20 |
On compare ensuite 60 à la clé 20 : on décale 60 d'une case à droite car 60 est plus grand.
| ↓ | ↓ | ||||
| Elément | 60 | 60 | 90 | 50 | 80 |
| 20 |
Encore une fois, il n'existe plus d'autres éléments à comparer avec la clé dans notre sous-tableau. On insère donc la clé à l'index 0 du tableau.
| Elément | 20 | 60 | 90 | 50 | 80 |
Nous avons maintenant un sous-tableau de trois éléments triés.
Etape suivante : on rajoute l'élément suivant
On rajoute 50 dans le sous-tableau.
| ↓ | |||||
| Elément | 20 | 60 | 90 | 50 | 80 |
Mettons la clé 50 en mémoire.
| ↓ | |||||
| Elément | 20 | 60 | 90 | 50 | 80 |
| 50 |
On compare 90 à la clé 50 : on décale 90 d'une case à droite car 90 est plus grand que la clé.
| ↓ | ↓ | ||||
| Elément | 20 | 60 | 90 | 90 | 80 |
| 50 |
On compare 60 à la clé 50 : on décale 60 d'une case à droite car 60 est plus grand que la clé.
| ↓ | ↓ | ||||
| Elément | 20 | 60 | 60 | 90 | 80 |
| 50 |
On compare 20 à la clé 50 : cette fois, la valeur n'est pas plus grande que la clé. On ne bouge pas la valeur mais on stoppe la recherche.
| ↓ | ↓ | ||||
| Elément | 20 | 60 | 60 | 90 | 80 |
| 50 |
Après avoir stoppé les décalages, on place la clé juste à droite de l'élément qui a provoqué l'arrêt.
| Elément | 20 | 50 | 60 | 90 | 80 |
Nous avons maintenant un sous-tableau de quatre éléments triés.
Dernière étape : on rajoute le dernier élément
On rajoute 80 dans le sous-tableau.
| ↓ | |||||
| Elément | 20 | 50 | 60 | 90 | 80 |
Mettons la clé 80 en mémoire.
| ↓ | |||||
| Elément | 20 | 50 | 60 | 90 | 80 |
| 80 |
01° Doit-on commencer à travailler avec 20 ou avec 90 ?
...CORRECTION...
On commence toujours par l'élément juste à gauche de la clé.
On commence donc d'abord par voir si on déplace 90 ou non.
02° QCM - Si la valeur sélectionnée est supérieure à la clé, que doit-on faire ?
- A : Placer la valeur dans la case juste à gauche
- B : Placer la valeur dans la case juste à droite
- C : Placer la clé dans la case juste à gauche
- D : Placer la clé dans la case juste à droite
On suppose bien entendu qu'on veut classer en ordre croissant.
...CORRECTION...
B : on place la valeur dans la case juste à droite de la position actuelle.
03° QCM - Si la valeur sélectionnée n'est pas supérieure à la clé, que doit-on faire ?
- A : Placer la valeur dans la case juste à gauche
- B : Placer la valeur dans la case juste à droite
- C : Placer la clé dans la case juste à gauche
- D : Placer la clé dans la case juste à droite
On suppose bien entendu qu'on veut classer en ordre croissant.
...CORRECTION...
D : on place la clé dans la case juste à droite de cette valeur qui ne lui est pas supérieure.
Voyons maintenant si vous avez bien compris le principe avec l'animation suivante qui vous montre le principe d'un tri par insertion.
Initialement, les premières valeurs correspondantes à celles de notre exemple.
| ↓ | ||||||||||||||||||||
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 90 | 60 | 20 | 50 | 80 | 10 | 90 | 99 | 30 | 90 | 70 | 10 | 20 | 70 | 98 | 30 | 40 | 90 | 90 | 60 |
04° Lancer l'animation qui intègre quelques explications. Cela devrait vous permettre de voir si vous avez compris le principe.
3 - Algorithme du tri par insertion
Dans la partie 1, vous avez vu le principe, réalisable par un humain.
Dans la partie 2, nous avons vu qu'il fallait parvenir à travailler sur les cases une par une si on veut parvenir à faire réaliser ce tri par un ordinateur.
Nous allons maintenant voir comment convertir chaque action décrite en Français en version algorithme.
Contrairement à un algorithme classique où le premier indice commence à 1, ici : Les éléments du tableau (de taille n) sont numérotés de 0 à n-1 .
Algorithme de tri par insertion
But : trier sur place un tableau initialement non trié.
(ici par odre croissant)
Description des entrées / sortie
ENTREES:tableau: un tableau contenant au moins deux éléments.- (optionnelle selon les langages d'implantation):
longueur, le nombre d'éléments dans le tableau SORTIE: aucune. Le tableau est trié sur place. On modifie directementtableau.
Exemple :
Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]
Initialement le tableau contient donc cela :
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Elément | 13 | 18 | 89 | 1024 | 45 | -12 | 18 |
Après le tri, le tableau contiendra cela :
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Elément | -12 | 13 | 18 | 18 | 45 | 89 | 1024 |
Principe en ordre croissant : si on doit expliquer avec des phrases l'animation ci-dessus, on pourrait dire cela :
- Pour chaque valeur (nommée clé) en partant de la gauche :
- On compare progressivement cette clé avec les éléments situés à gauche de la clé. On part de celui ayant l'index juste inférieur.
- Si la clé est strictement supérieure à l'élément lu, on décale l'élément d'une case à droite dans le tableau .
- Sinon, on place la clé dans la case juste à droite de l'élément actuel.
Voyons maintenant comment parvenir à réaliser cela avec un algorithme.
En Français
- Pour chaque valeur (nommée clé) en partant de la gauche :
En Algorithme
i est l'index (flèche en vert clair dans l'animation) de la clé-valeur qu'il faut placer
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
on mémorise dans cle la valeur-clé car cette case risque d'être écrasée
05° Pourquoi commencer par l'index 1 pour trouver la clé et pas par l'index 0 ?
...CORRECTION...
On commence par un sous-tableau d'un élément, celui d'index 0.
Ici, on commence à rajouter d'autres éléments un par un. On commence donc par rajouter celui d'index 1.
En Français
- Pour chaque valeur (nommée clé) en partant de la gauche :
- On compare progressivement cette clé avec les éléments situés à gauche de la clé. On part de celui ayant l'index juste inférieur.
En Algorithme
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
j ← i - 1
La variable j contient initialement l'index juste à gauche de la clé (flèche verte dans l'animation)
06° L'index de la valeur qu'on veut comparer à la clé est notée ici j . C'est la flèche verte de l'animation. Quelle est l'information dans l'énoncé en Français qui correspond à l'initialisation de la variable j à i - 1 ?
...CORRECTION...
On demande à commencer par la case juste à gauche de la clé.
Par exemple, si la clé correspond actuellement à l'index i = 5, il faudra donc commencer par surveiller la valeur sur l'index juste inférieur donc j = 4 = 5 - 1.
Reste à voir l'histoire des comparaisons :
En Français
- Pour chaque valeur (nommée clé) en partant de la gauche :
- On compare progressivement cette clé avec les éléments situés à gauche de la clé. On part de celui ayant l'index juste inférieur.
En Algorithme
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
j ← i - 1
TANT QUE j ≥ 0 et que tableau[j] > cle
j ← j - 1
On passe à la case suivante à gauche
Fin TANT QUE
07° Répondre aux trois questions suivantes :
- Pourquoi faire diminuer j de 1 à chaque tour de boucle ?
- Pourquoi placer une condition
j ≥ 0? - Pourquoi ne pas avoir écrit plutôt la condition dans l'autre sens :
tableau[j] > cleet que j ≥ 0
...CORRECTION...
1 : On diminue j de 1 à chaque tour de boucle pour parvenir à gérer un par un les éléments à gauche de la clé. Si la clé est d'index 5, on gére donc l'élément d'index 4, puis 3, puis 2...
2 : il faut tester que l'index de l'élément soit bien supérieur ou égal à 0 sous peine d'être hors tableau. En Python, c'est même pire : -1 ne va pas déclencher d'erreur mais cela veut dire d'aller lire le dernier élément du tableau...
3 : On se souviendra des expressions pareusseuses. Si la première condition est fausse, comme c'est un ET, on ne regarde pas la deuxième. Si on teste dans l'autre sens, il y a un risque d'avoir un index de -1 et de demander à lire néanmoins tableau[-1].
Voyons les actions à réaliser si la valeur est plus grande que la clé.
En Français
- POUR chaque valeur du tableau en commençant par la gauche :
- On nomme clé la valeur en cours d'étude
- On compare progressivement la clé avec les valeurs situées à sa gauche. On commmence par celle située juste au côté.
- Si l'élément lu est strictement supérieure à la clé, on décale l'élément d'une case à droite dans le tableau.
En Algorithme
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
j ← i - 1
TANT QUE j ≥ 0 et que tableau[j] > cle
tableau[j+1] ← tableau[j]
j ← j - 1
Fin TANT QUE
✎ 08° Que réalise l'instruction surlignée en jaune ?
Voyons les actions à réaliser si la valeur n'est pas plus grande que la clé.
En Français
- Pour chaque valeur (nommée clé) en partant de la gauche :
- On compare progressivement cette clé avec les éléments situés à gauche de la clé. On part de celui ayant l'index juste inférieur.
- Si la clé est strictement inférieure à l'élément lu, on décale l'élément d'une case à droite dans le tableau .
- Sinon, on place la clé dans la case juste à droite de l'élément actuel.
En Algorithme
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
j ← i - 1
TANT QUE j ≥ 0 et que tableau[j] > cle
tableau[j+1] ← tableau[j]
j ← j - 1
Fin TANT QUE
tableau[j+1] ← cle
On place la valeur-clé à la place voulue pour obtenir un sous-tableau trié
09° Justifier le fait qu'on exécute tableau[j+1] ← cle , le placement de la cle, dans deux cas. Pour trouver ces deux cas, il faut aller regarder la condition du TANT QUE.
Vérifier que vous avez bien répondu en précisant ce que va se passer une fois qu'on a lu tous les éléments du sous-tableau.
...CORRECTION...
La condition est TANT QUE j ≥ 0 et que tableau[j] > cle
Nous allons donc exécuter tableau[j+1] ← cle , le placement de la clé dans l'index à droite de j lorsqu'on sortira du TANT QUE. C'est à dire soit i :
j = -1: on vient de sortir du tableau. Dans ce cas, on placera la clé à la première place, dans l'index 0 (car -1 + 1). Ce cas arrive lorsque la clé est plus petite que toutes les autres valeurs.- La valeur stockée dans
tableau[j]n'est pas supérieure àcle. Dans ce cas, on placera la clé à droite de cette valeur.
Et voilà. Nous avons fini. Comme il s'agit d'une procédure, on peut au pire préciser que notre algorithme ne renvoie rien.
Algorithme de tri par insertion, commenté
i est l'index (flèche en vert clair dans l'animation) de la clé-valeur qu'il faut placer
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
on mémorise dans cle la valeur-clé car cette case risque d'être écrasée
j ← i - 1
La variable j contient initialement l'index juste à gauche de la clé (flèche verte dans l'animation)
TANT QUE j ≥ 0 et que tableau[j] > cle
tableau[j+1] ← tableau[j]
On décale la valeur d'une case à droite
j ← j - 1
On passe à la case suivante à gauche
Fin TANT QUE
tableau[j+1] ← cle
On place la valeur-clé à la place voulue pour obtenir un sous-tableau trié
Fin POUR
Renvoyer VIDE (∅)
Algorithme de tri par insertion, non commenté
POUR i variant de 1 à (longueur - 1)
cle ← tableau[i]
j ← i - 1
TANT QUE j ≥ 0 et que tableau[j] > cle
tableau[j+1] ← tableau[j]
j ← j - 1
Fin TANT QUE
tableau[j+1] ← cle
Fin POUR
Renvoyer VIDE (∅)
Voici l'animation précédente mais en y notant les "positions" des variables i et j.
Vous remarquerez que lorsqu'on va tout à gauche, la variable j contient une valeur non valide directement d'index : -1.
| ↓ | ||||||||||||||||||||
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
10° Lancer l'animation. Visualiser qu'avec notre algorithme, on place TOUJOURS la clé juste à droite de la valeur de j lorsqu'on vient de sortir de la boucle TANT QUE.
4 - Tri par insertion en Python
Tri par insertion d'un tableau (ordre croissant, avec commentaires, documentation et doctest)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | def tri_par_insertion(tableau) :
'''Tri en ordre croissant le tableau en utilisation le tri par insertion
:: param tableau(list) :: un tableau d'éléments de même type
:: return (None) :: procédure (renvoie donc None en Python)
.. Effet de bord :: modifie le tableau en permutant les éléments
:: precondition :: tableau doit contenir au moins deux éléments
:: precondition :: les éléments de tableau doivent pouvoir être comparés entre eux
:: exemple ::
>>> numeros = [5, 8, 1, 20, 15]
>>> tri_par_insertion(numeros)
>>> numeros
[1, 5, 8, 15, 20]
'''
for i in range(1, len(tableau)) :
cle = tableau[i]
j = i - 1 # On commence par l'élément juste à gauche de la clé
while j >= 0 and tableau[j] > cle :
tableau[j+1] = tableau[j] # On décale l'élément vers la droite
j = j - 1 # On passe à l'élément encore à gauche
tableau[j+1] = cle
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Dans le programme ci-dessus, nous utilisons des commentaires et un doctest.
11° Consulter le document Tester avec un doctest .
Lire et faire les exercices demandés.
12°Copier le programme dans spyder et le sauvegarder.
Tapez les instructions suivantes dans la console pour visualiser le résultat.
>>> donnees = [5, 2, 12, 18, 199, 50]
>>> tri_par_insertion(donnees)
>>> donnees
[2, 5, 12, 18, 50, 199]
✎ 13° Utiliser notre fonction pour trier le tableau ci-dessous. Vous donnerez le résultat dans le fichier à rendre.
>>> donnees = [577, 334, 443, 938, 49, 678, 696, 841, 54, 552, 30, 688, 288, 716, 663, 987, 826, 701, 875, 381, 427, 910, 758, 55, 977, 951, 941, 443, 399, 695, 732, 905, 538, 476, 185, 299, 849, 196, 942, 599, 953, 570, 100, 40, 852, 185, 825, 23, 413, 766, 952, 518, 583, 695, 772, 63, 911, 915, 838, 444, 118, 813, 855, 527, 35, 269, 222, 992, 956, 102, 840, 55, 377, 95, 260, 390, 543, 206, 887, 825, 44, 373, 881, 364, 588, 843, 993, 200, 765, 695, 518, 21, 983, 894, 271, 854, 190, 480, 776, 952, 13, 261, 516, 922, 399, 874, 474, 968, 29, 475, 435, 132, 761, 753, 435, 431, 568, 838, 454, 975, 925, 981, 840, 198, 240, 410, 825, 468, 554, 545, 771, 839, 10, 293, 578, 702, 46, 971, 380, 906, 49, 894, 265, 350, 965, 873, 174, 743, 273, 270, 807, 253, 301, 537, 157, 508, 656, 584, 210, 705, 985, 872, 592, 26, 463, 285, 79, 93, 186, 887, 289, 787, 630, 889, 558, 81, 34, 197, 787, 947, 878, 804, 538, 699, 845, 249, 44, 86, 476, 755, 517, 157, 523, 286, 666, 970, 938, 67, 196, 948]
Le plus beau avec ce tri, c'est qu'il suffit d'inverser la comparaison de la ligne 21 (> en <) pour trier par ordre décroissant.
✎ 14° Modifier la fonction pour trier le tableau ci-dessous en ordre décroissant cette fois. Ne modifiez pas le doctest pour l'instant. Fournir le résultat obtenue à l'écran.
>>> donnees = [577, 334, 443, 938, 49, 678, 696, 841, 54, 552, 30, 688, 288, 716, 663, 987, 826, 701, 875, 381, 427, 910, 758, 55, 977, 951, 941, 443, 399, 695, 732, 905, 538, 476, 185, 299, 849, 196, 942, 599, 953, 570, 100, 40, 852, 185, 825, 23, 413, 766, 952, 518, 583, 695, 772, 63, 911, 915, 838, 444, 118, 813, 855, 527, 35, 269, 222, 992, 956, 102, 840, 55, 377, 95, 260, 390, 543, 206, 887, 825, 44, 373, 881, 364, 588, 843, 993, 200, 765, 695, 518, 21, 983, 894, 271, 854, 190, 480, 776, 952, 13, 261, 516, 922, 399, 874, 474, 968, 29, 475, 435, 132, 761, 753, 435, 431, 568, 838, 454, 975, 925, 981, 840, 198, 240, 410, 825, 468, 554, 545, 771, 839, 10, 293, 578, 702, 46, 971, 380, 906, 49, 894, 265, 350, 965, 873, 174, 743, 273, 270, 807, 253, 301, 537, 157, 508, 656, 584, 210, 705, 985, 872, 592, 26, 463, 285, 79, 93, 186, 887, 289, 787, 630, 889, 558, 81, 34, 197, 787, 947, 878, 804, 538, 699, 845, 249, 44, 86, 476, 755, 517, 157, 523, 286, 666, 970, 938, 67, 196, 948]
✎ 15° Modifier maintenant le doctest et fournir la fonction correctement modifiée pour trier en ordre décroissant.
Voici le fonctionnement visuel de l'algorithme en mode décroissant :
| ↓ | ||||||||||||||||||||
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
5 - FAQ
Comment appliquer cet algorithme à une collection ?
Il fonctionne de la même manière. La seule différence vient du fait qu'on a besoin d'un paramètre supplémentaire : le descripteur à surveiller. Il s'agit de la clé du dictionnaire à surveiller s'il s'agit d'une collection de dictionnaire ou le numéro d'index à surveiller s'il s'agit d'une collection de tuples ou de tableaux.
On notera que nous avons vu des méthodes permettant de faire cela en utilisant la méthode sort et les opérateurs.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | def tri_par_insertion(collection, descripteur, ordre=True) :
'''Tri en ordre la collection en utilisation le tri par insertion
:: param collection(list) :: un tableau de dictionnaire, de tuples ou de tableaux
:: param descripteur(divers) :: un descripteur valide de la collection
:: param ordre(bool) :: True pour croissant, False pour décroissant
:: return (None) :: procédure (renvoie donc None en Python)
.. Effet de bord :: modifie la colllection en permutant les éléments
:: precondition :: collection doit contenir au moins deux éléments qui partagent les mêmes descripteurs
:: precondition :: le descripteur doit permettre de comparer
'''
for i in range(1, len(collection)) :
cle = collection[i]
j = i - 1 # On commence par l'élément juste à gauche de la clé
if ordre :
while j >= 0 and collection[j][descripteur] > cle[descripteur] :
collection[j+1] = collection[j] # On décale l'élément vers la droite
j = j - 1 # On passe à l'élément encore à gauche
collection[j+1] = cle
else :
while j >= 0 and collection[j][descripteur] < cle[descripteur] :
collection[j+1] = collection[j] # On décale l'élément vers la droite
j = j - 1 # On passe à l'élément encore à gauche
collection[j+1] = cle
|
Voici un exemple pour la forme, avec des Pokemons.
>>> collection = []
>>> collection.append({'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'})
>>> collection.append({'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'})
>>> collection.append({'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'})
>>> collection.append({'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'})
>>> collection
[
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'},
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'}
]
>>> tri_par_insertion(collection, 'HP', ordre=True)
>>> collection
[
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'},
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'}
]
>>> tri_par_insertion(collection, 'HP', ordre=False)
>>> collection
[
{'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
]
Comment faire sans créer nous même une fonction ?
Nous avions utilisé la méthode sort pour trier la collection sur place.
Le tout est de lui indiquer de trier en fonction de la clé de dictionnaire voulu.
La version avec la fonction itemgetter.
1
2
3
4
5
6
7
8
9
10 | from operator import itemgetter
pokemons = [
{'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
]
pokemons.sort(key=itemgetter('HP'), reverse=False)
|
Et la version avec une fonction lambda.
1
2
3
4
5
6
7
8 | pokemons = [
{'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
]
pokemons.sort(key=lambda item:item['HP'], reverse=True)
|
On notera qu'ici j'ai indiqué de trier en ordre inverse (décroissant). Si vous voulez trier dans l'ordre croissant, il suffit de ne pas transmettre reverse ou de lui donner une valeur fausse.
Activité publiée le 18 05 2020
Dernière modification : 12 04 2021
Auteur : ows. h.
Modifié par : Andjekel.