Algo Tri par insertion

Identification

Infoforall

Animation du tri par insertion


Cette page présente une animation permettant de comprendre le principe du tri par insertion.

On y présente aussi l'algorithme et une version en Python.

1 - Animation

Ce tri se fait en modifiant le contenu du tableau initial. La place mémoire nécessaire est donc assez faible. On dit qu'on trie le tableau sur place.

Le principe est de trier progressivement le tableau de la gauche vers la droite.

La partie rouge correspond à la portion du tableau qui n'est pas encore trié. On déplace alors les éléments déjà triés pour permettre à l'élément non trié suivant de trouver sa place.

Tri par insertion (ordre croissant)

On décale les éléments d'une case à droite tant qu'ils sont supérieurs à la clé à trier.

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

Tri par insertion (ordre décroissant)

On décale les éléments d'une case à droite tant qu'ils sont inférieurs à la clé à trier.

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

2 - Algorithmes

On présente l'algorithme de tri par insertion.

Algorithme de tri par insertion

But : trier (ici par odre croissant) un tableau initialement non trié.

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 dans le tableau l'élément d'une case à droite.
      • Sinon, on place la clé dans la case juste à droite de l'élément actuel.

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

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

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

On notera en ligne 22 que la comparaison utilise > pour l'ordre croissant.

Tri par insertion d'un tableau (ordre décroissant, sans commentaire, documentation ou doctest)

La seule différence en ordre décroissant est sur le test de la ligne 5 : cette fois, la comparaison est faite en utilisant <.

1 2 3 4 5 6 7 8
def tri_par_insertion(tableau) : for i in range(1, len(tableau)) : cle = tableau[i] j = i - 1 while j >= 0 and tableau[j] < cle : tableau[j+1] = tableau[j] j = j - 1 tableau[j+1] = cle

Article publié le 26 04 2020
Dernière modification : 26 04 2020
Auteur : ows. h.