Algo Insertion

Identification

Infoforall

7 - tri par insertion


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

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 8 de Coeur 9 de Coeur 4 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.

vide vide vide 4 de Coeur
2 de Coeur 8 de Coeur 9 de Coeur vide

Spontanément, on va laisser le 2 en place mais on va décaler le 8 et le 9.

vide vide vide 4 de Coeur
2 de Coeur vide 8 de Coeur 9 de Coeur

Et voilà : il ne reste plus qu'à mettre le 4 entre le 2 et le 8.

2 de Coeur 4 de Coeur 8 de Coeur 9 de Coeur

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

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.

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

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)

      cletableau[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)

      cletableau[i]

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

      cletableau[i]

      ji - 1

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

        jj - 1

        On passe à la case suivante à gauche

      Fin TANT QUE

07° Répondre aux trois questions suivantes :

  1. Pourquoi faire diminuer j de 1 à chaque tour de boucle ?
  2. Pourquoi placer une condition  j ≥ 0  ?
  3. Pourquoi ne pas avoir écrit plutôt la condition dans l'autre sens : tableau[j] > cle et 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 (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 .
    En Algorithme

    POUR i variant de 1 à (longueur - 1)

      cletableau[i]

      ji - 1

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

        tableau[j+1]tableau[j]

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

      cletableau[i]

      ji - 1

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

        tableau[j+1]tableau[j]

        jj - 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 :

  1.  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.
  2. 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)

      cletableau[i]

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

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

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

      cletableau[i]

      ji - 1

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

        tableau[j+1]tableau[j]

        jj - 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()

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 :

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.

Nous avons donc vu l'algorithme de tri par insertion en pratique.

L'activité suivante permettra de justifier son fonctionnement correct et permettra de trouver sa complexité dans le meilleur des cas et dans le pire des cas.

Activité publiée le 27 04 2020
Dernière modification : 27 04 2020
Auteur : ows. h.