Tri par insertion

Principe

Visionner la séquence vidéo proposée. Lien

Le tri par insertion est le tri effectué par le joueur de carte. En supposant que l'on maintienne une partie triée, on décale les cartes de cette partie, de manière à placer la carte à classer (voir video).

En informatique, on va très souvent travailler avec un tableau et le parcourir de la gauche vers la droite, en maintenant la partie déjà triée sur sa gauche (voir lien wikipedia).
Concrètement, on va décaler d'une case vers la droite tous les éléments déjà triés, qui sont plus grands que l'élément à classer, puis déposer ce dernier dans la case libérée.

Algorithme

1
2
3
4
5
6

Algorithme Tri_insertion(t)
---------------------------
t: tableau de n éléments comparables (t[0..n-1])

Pour i allant de 1 à n-1:
    amener t[i] à sa place parmi t[0..i-1]

Implémentation en python

On commence par donner une réalisation de amener t[i] à sa place parmi t[0..i-1] en écrivant une fonction place(t, i) qui amène l'élément d'index $i$ à sa place parmi les éléments d'index 0 à $i-1$ déjà classés.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def place(t, i):
    """ amène t[i] à sa place dans t[0..i-1] supposé trié"""
    elt_a_classer = t[i]
    j = i
    # décalage des éléments du tableau à droite, pour trouver la place de t[i]
    while j > 0 and t[j - 1] > elt_a_classer:
        t[j] = t[j - 1]
        j = j - 1
    # on insère l'élément à sa place
    t[j] = elt_a_classer

1
2
3

def insertion(t):
    # compléter le code de la fonction insertion(t), sans oublier la spécification
    pass

1
2
3
4

# Test
t = [7, 2, -3, 5]
insertion(t)
assert t == [-3, 2, 5, 7]

Validité de l'algorithme

L'algorithme Tri_insertion termine car il présente une boucle bornée. La boucle conditionnelle présente dans la réalisation amener t[i] à sa place parmi t[0..i-1] termine également, la quantité $j$ étant un variant de boucle.

De manière intuitive, on comprend qu'à chaque tour de boucle on se rapproche de la solution recherchée. On agrandit la zone triée de un élément. Exhiber une telle propriété (un invariant de boucle) permet de conclure à la correction partielle de l'algorithme.

La combinaison de la correction partielle avec la terminaison permet de conclure à la correction totale de l'algorithme Tri_insertion.

Efficacité: complexité temporelle de l'algorithme

Afin d'évaluer le coût de l'algorithme dans le pire des cas, on doit s'intéresser aux nombre d'opérations effectuées, qui est ici lié au nombre de décalage avant de trouver la place de l'élément à classer. Le pire des cas se produit lorsque le tableau est classé en sens inverse. Visualisons cela sur un tableau à 5 éléments, simple à trier: t = [5, 4, 3, 2, 1].

Le nombre de décalage nécessaire est: $1 + 2 + 3 + 4 = 10$.

On généralise sans peine: dans le pire des cas, pour un tableau de taille n, il faudra effectuer:

$$1+2+\cdots + (n-2) + (n-1)=\dfrac{n}{2}\times(n-1)$$

décalages. Comme pour le tri par sélection, le coût (on dit aussi complexité) en temps du tri par insertion, dans le pire des cas, est quadratique. On dit aussi que la complexité est en $O(n²)$.