10 - tri par insertion

⏪

⏬

⏩

1 - Cartes

2 - Principe

3 - Algorithme

4 - Python

5 - FAQ

Nous avons vu que la recherche dichotomique ou l'algorithme knn nécessitent 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.

Mais comment ça fonctionne ?

Nous allons voir aujourd'hui une méthode de tri, le tri par insertion.

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...

Prérequis : les activités suivantes

Algorithme : parcours séquentiel d'un tableau,

Evaluation ✎ : questions 08-12-13-14

Résumé de cours : open document ou pdf

MODE COURS (cacher les questions)

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.

2 de Coeur — Images dans le domaine public issues de https://publicdomainvectors.org

8 de Coeur — Images dans le domaine public issues de https://publicdomainvectors.org

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 9 car il est plus grand que le 4.

On passe à la carte suivante : le 8. On la décale également car elle est plus grande que le 4.

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'indice 0 et l'indice 1 d'un tableau !

La méthode que nous allons expliquer réalise donc ceci :

Mettre le 4 en mémoire dans une variable temporaire.
En boucle : décaler les cartes supérieures à 4 d'une case à droite dans le tableau (case d'indice + 1 donc). C'est pour cela qu'il faut mémoriser qu'on veut placer un 4 : sans cette mémoire, notre 4 se ferait juste écraser et l'information aurait disparu... Dans le programme, on ne déplace pas réellement un objet physique, on copie juste un contenu-mémoire dans un autre contenu-mémoire.

Situation mémoire avant le premier décalage :

Situation mémoire après le premier décalage si on ne mémorise pas le 4 ailleurs...

Mettre le 4 dans la case d'indice "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 ne contenant (pour l'instant) qu'un seul élément. Le tableau bleu est donc trié, puisqu'il n'a qu'un seul élément !.

	↓
Elément	90	60	20	50	80

Etape 2 (en boucle): on rajoute l'élément suivant

Nous rajouter une case à la fin du tableau bleu et nous y placer le 60. On nommera cette valeur qu'on veut placer correctement la clé.

		↓
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 donc 90 à 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'indice 1.

Il n'y a plus d'autres valeurs à surveiller. On place alors la clé sur l'indice 0.

Elément

A la fin de ce tour de boucle, nous avons un sous-tableau bleu de deux éléments triés.

Retour au début de la boucle : 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'indice 0 du tableau.

Elément

Nous avons maintenant un sous-tableau de trois éléments triés.

Tour de boucle suivant : 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

Nous avons maintenant un sous-tableau de quatre éléments triés.

Tour de boucle suivant : 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 la case contenant 20 ou avec 90 ?

Correction ?

...CORRECTION...

On commence toujours par l'élément juste à gauche de la clé (indice inférieur de 1 donc).

On commence donc d'abord par voir si on déplace 90 ou non.

02° QCM - Si la valeur de la case en cours est supérieure à la valeur de la clé, que doit-on faire ?

Placer la valeur en cours dans la case juste à gauche
Placer la valeur en cours dans la case juste à droite
Placer la clé dans la case juste à gauche
Placer la clé dans la case juste à droite

Correction ?

...CORRECTION...

B : on place la valeur dans la case juste à droite de la position actuelle.

03° QCM - Si la valeur de la case en cours 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

Correction ?

...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.


indice	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.

Algorithme de tri par insertion

But : trier un tableau (ici par odre croissant)

Description des entrées / sortie

ENTREES :

t : un tableau NON VIDE.
(selon les langages d'implémentation) : longueur, le nombre d'éléments dans le tableau

SORTIE : aucune. Le tableau est trié sur place.

Exemple :

Prenons t = [13, 18, 89, 1024, 45, -12, 18]

Initialement le tableau contient donc cela :

indice	0	1	2	3	4	5	6
Elément	13	18	89	1024	45	-12	18

Après le tri, le tableau contiendra cela :

indice	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 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 la clé est strictement supérieure à la carte lue, on décale cette carte 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 du tableau en commençant par la gauche :

On nomme clé la valeur en cours d'étude

En Algorithme

i est l'indice (flèche en vert clair dans l'animation) de la clé-valeur qu'il faut placer

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[i]

on mémorise dans cle la valeur-clé car cette case risque d'être écrasée

05° Pourquoi commencer par l'indice 1 pour trouver la clé et pas par l'indice 0 ?

Correction ?

...CORRECTION...

On commence par un sous-tableau d'un élément, celui d'indice 0.

Ici, on commence à rajouter d'autres éléments un par un. On commence donc par rajouter celui d'indice 1.

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é.

En Algorithme

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[i]

j ← i - 1

La variable j contient initialement l'indice juste à gauche de la clé (flèche verte dans l'animation)

06° L'indice 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 ?

...CORRECTION...

On demande à commencer par la case juste à gauche de la clé.

Par exemple, si la clé correspond actuellement à l'indice i = 5, il faudra donc commencer par surveiller la valeur sur l'indice juste inférieur donc j = 4 = 5 - 1.

Reste à voir l'histoire des comparaisons :

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é.

En Algorithme

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[i]

j ← i - 1

TANT QUE j ≥ 0 et que t[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 : t[j] > cle et que j ≥ 0

Correction ?

...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'indice 5, on gére donc l'élément d'indice 4, puis 3, puis 2...

2 : il faut tester que l'indice 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 indice de -1 et de demander à lire néanmoins t[-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 la clé est strictement supérieure à l'élément lu, on décale l'élément d'une case à droite dans le tableau.

En Algorithme

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[i]

j ← i - 1

TANT QUE j ≥ 0 et que t[j] > cle

t[j+1] ← t[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 suivante n'est pas 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 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.

En Algorithme

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[i]

j ← i - 1

TANT QUE j ≥ 0 et que t[j] > cle

t[j+1] ← t[j]

j ← j - 1

Fin TANT QUE

t[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 t[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 ?

...CORRECTION...

La condition est TANT QUE j ≥ 0 et que t[j] > cle

Nous allons donc exécuter t[j+1] ← cle , le placement de la clé dans l'indice à 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'indice 0 (car -1 + 1). Ce cas arrive lorsque la clé est plus petite que toutes les autres valeurs.
La valeur stockée dans t[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'indice (flèche en vert clair dans l'animation) de la clé-valeur qu'il faut placer

POUR i variant de 1 à (longueur - 1) inclus

cle ← t[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'indice juste à gauche de la clé (flèche verte dans l'animation)

TANT QUE j ≥ 0 et que t[j] > cle

t[j+1] ← t[j]

On décale la valeur d'une case à droite

j ← j - 1

On passe à la case suivante à gauche

Fin TANT QUE

t[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) inclus

cle ← t[i]

j ← i - 1

TANT QUE j ≥ 0 et que t[j] > cle

t[j+1] ← t[j]

j ← j - 1

Fin TANT QUE

t[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'indice : -1.


indice	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)

def tri_par_insertion(t):
    """Tri en ordre croissant le tableau en utilisation le tri par insertion
 
    :: param t(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 :: t doit contenir au moins deux éléments
    :: precondition :: les éléments de t 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(t)):
        cle = t[i]
        j = i - 1 # On commence par l'élément juste à gauche de la clé
        while j >= 0 and t[j] > cle:
            t[j+1] = t[j] # On décale l'élément vers la droite
            j = j - 1 # On passe à l'élément encore à gauche
        t[j+1] = cle
 
if __name__ == '__main__':
    import doctest
    doctest.testmod()

11° Placer le programme en mémoire.

Tapez les instructions suivantes en mémoire pour visualiser le résultat.


>>> donnees = [5, 2, 12, 18, 199, 50]
>>> tri_par_insertion(donnees)
>>> donnees
[2, 5, 12, 18, 50, 199]

✎ 12° Utiliser notre fonction pour trier le tableau ci-dessous. Vous donnerez le résultat sur votre copie numérique.


>>> 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.

✎ 13° 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.


>>> 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]

✎ 14° 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 :


indice	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'indice à 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.

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.

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.

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 27 04 2020
Dernière modification : 19 09 2020
Auteur : ows. h.

⏪

⏫

⏩