Animation du tri par insertion

⏬

1 - Animation

2 - Algorithmes

3 - Python

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'implémentation): 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)

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

3 - Python

⇩ ⇧ ⤊

Tri par insertion d'un tableau (ordre croissant, avec commentaires, documentation et doctest)

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

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.

⏫