Tri par insertion

Un article de HanLee.

Nous utiliserons ici les notations présentées dans le sommaire de l'article. On pose bien évidemment R = ≤.

[modifier] Préliminaires

Avant de commencer, introduisons la fonction pos, une fonction auxiliaire prenant en argument :

• t : un vecteur existant d'éléments de type T (appelé t pour ne pas créer de confusion avec nos notations précédentes)
• g : un entier représentant la limite gauche de la zone du vecteur t que la fonction pos devra traiter (le vecteur étant numéroté de 0 à n-1). Attention aux bornes du vecteur !
• d : un entier représentant la limite droite de la même zone précédemment décrite avec g ≤ d. Attention aux bornes du vecteur !
• E : un élément de type T

et qui retourne un entier.

Hypothèse :

t est complètement rangé selon la relation d'ordre ≤ dans la zone comprise entre g et d, soit dit manière grossière : t[g] ≤ t[g+1] ≤ ... ≤ t[d].

Fonctionnement :

pos indique la position à laquelle il faut insérer E dans le vecteur dans la zone délimitée par g et d, si l'on souhaite conserver l'ordre des éléments selon ≤.
S'il est impossible d'insérer E entre g et d, alors pos renvoie d+1.

Exemples :

Soit le vecteur V égal à [3 ; 6 ; 14 ; 20 ; 16].
pos(V, 0, 2, 2) renvoie alors 0
pos(V, 1, 3, 21) renvoie alors 4.

[modifier] Principe de l'algorithme

L'algorithme de tri par insertion repose sur un principe simple : il s'agit d'insérer progressivement et dans le bon ordre des éléments dans un vecteur qui s'agrandit au fur et à mesure des ajouts des éléments. Nul besoin d'un vecteur temporaire, il est parfaitement possible de travailler directement sur le vecteur à trier.

[modifier] Principe

• Si v ne comporte qu'un seul élément, ce n'est évidemment pas la peine de tenter de le réordonner car il l'est déjà !
  
• Sinon pour tout élément de v, d'indice i variant de 1 à n-1, si le vecteur y est défini, on l'insère à la bonne position donnée par pos(v, 0, i-1, v[i]), dans le début du vecteur v (entre 0 à i).
  Comment ? Si lim est la valeur renvoyée par pos(v, 0, i-1, v[i]) et E la valeur présente de v[i], on décale les éléments des indices lim à i-1 vers lim+1 à i, puis on affecte à v[lim] la valeur de E.

[modifier] Exemple

Pour comprendre rapidement, rien ne vaut un petit exemple.
Prenons un vecteur v tel que ses éléments sont : [3 ; 9 ; 6 ; 11 ; 7 ; 1].

• v[0] forme à lui seul un vecteur d'un élément, il est donc déjà entièrement ordonné.
  Considérons v[1], posons lim = pos(v, 0, 0, v[1]) et E = v[1], lim vaut 1 car 9 > 3 (ou encore E > v[0]).
  Il n'y a donc rien à modifier pour l'instant, mais on peut d'ores et déjà se dire que v est trié entre ses indices 0 et 1.
  v reste égal à [3 ; 9 ; 6 ; 11 ; 7 ; 1].

• Regardons maintenant v[2], puis posons lim = pos(v, 0, 1, v[2]) et E = v[2], lim vaut 1 car 6 ≤ 9 (E ≤ v[1]).
  Nous décalons alors tous les éléments de v des indices lim = 1 à 1 vers les indices lim+1 = 2 à 1+1 = 2, puis nous affectons à v[lim] = E la valeur de E.
  v vaut alors [3 ; 6 ; 9 ; 11 ; 7 ; 1].

• Regardons v[3], il n'y a rien à modifier.
  v reste égal à [3 ; 6 ; 9 ; 11 ; 7 ; 1].

• Regardons v[4], lim vaut 2, E vaut 7.
  On décale les éléments de v des indices lim = 2 à 3 vers les indices lim+1 = 3 à 3+1 = 4, puis on fait v[2] <- E.
  v vaut alors [3 ; 6 ; 7 ; 9 ; 11 ; 1].

• On décale les 5 premiers éléments vers la droite d'un cran, on met en position 0 la valeur 1.
  v vaut alors [1 ; 3 ; 6 ; 7 ; 9 ; 11].

Le vecteur v est maintenant trié !

[modifier] L'algorithme

L'algorithme est très court et très simple. Le seul point délicat est de faire attention aux indices du vecteur.

i, j, limite, tmp de type Entier

Pour i de 1 à n-1 Faire
{
    // On récupère la position où insérer l'élément v[i] entre 0 et i
    // Le '+ 1' sert au bon fonctionnement de la boucle qui suit
    limite <- pos(v, 0, i-1, v[i]) + 1
    // On sauvegarde dans une variable temporaire v[i] qui va être
    // effacé par le décalage
    tmp    <- v[i]

    // Si besoin, on décale d'un cran des éléments vers la droite
    Pour j de i à limite Incrément -1 Faire
    {
        // On déplace la valeur de v[j-1] vers v[j]
        v[j] <- v[j-1]
    }

    v[limite - 1] <- tmp
}

[modifier] La fonction pos

L'algorithme de la fonction pos a volontairement été omis dans les préliminaires, afin de rendre l'explication de l'algorithme de tri la plus claire possible.
De plus, il existe plusieurs algorithmes pour cette fonction, 2 principalement. L'une est beaucoup plus efficace que l'autre, et c'est ce qui explique le fait qu'il existe 2 méthodes de tri par insertion.

[modifier] Insertion simple

Cet algorithme s'exécute en temps linéaire, on parcourt t séquentiellement des indices g à d, c'est-à-dire qu'on regarde tous les éléments du vecteur à la suite.

Fonction pos(t, g, d, E)
{
    i type Entier

    Pour i de g à d Faire
    {
        Si E ≤ t[i] Alors
        {
            Retourne i
        }
    }

    Retourne d + 1
}

[modifier] Insertion dichotomique

Cet algorithme s'exécute en temps logarithmique, en utilisant l'hypothèse comme quoi le vecteur t était déjà ordonné entre g et d.
Si g ≠ d, on divise en fait en 2 une première fois le vecteur entre g et d, puis avec un test, on détermine entre les 2 parties, la position où insérer l'élément E. On réitère le processus sur la partie déterminée, et cela plusieurs fois jusqu'à ce que les parties trouvées se réduisent à une zone d'un seul élément.

L'algorithme se prête très bien à une implémentation récursive :

Fonction pos(t, g, d, E)
{
    Si g = d Alors
    {
        Si g ≤ E Alors
            Retourne g + 1
        Sinon
            Retourne g
    }
    SinonSi t[(g + d) / 2] ≤ E Alors
        Retourne pos(t, (g+d)/2, d, E)
    Sinon
        Retourne pos(t, g, (g+d)/2, E)
}

mais on peut facilement la transformer en une version itérative :

Fonction pos(t, g, d, E)
{
    TantQue g ≠ d Faire
    {
        Si t[(g + d) / 2] ≤ E Alors
            g <- (g+d)/2 + 1
        Sinon
            d <- (g+d)/2
    }

    Si t[g] ≤ E Alors
        Retourne g + 1
    Sinon
        Retourne g
}

Retour à la page principale