Algorithme du tri par insertion

Cours/Algorithmie/Problème du tri/Algorithme du tri par insertion

Le tri par insertion est un exemple d'algorithmes dont les complexité minimum et maximum sont très différentes. Il est alors nécessaire de calculer la complexité en moyenne pour avoir une idée de la complexité attendu pour un tableau aléatoire (ie inconnu).

Cet algorithme est une extension de l'algorithme est_trie. Plutôt que de rendre False il répare. L'algorithme est_trie répond False au plus petit i tel que T[i] < T[i-1]. On est alors dans le cas où :

T[:i] est trié
et T[i] < T[i-1]

Pour que l'on puisse continuer, il faut s'arranger pour que T[:i+1] soit trié. Pour cela, on peut utiliser le fait que T[:i+1] est trié si et seulement si :

T[1] >= T[0]
T[2] >= T[1]
...
T[i] >= T[i-1]

Dans notre cas, toutes les conditions sont vérifiées sauf la dernière. Si l'on échange T[i] et T[i-1] toutes les conditions seront vérifiées sauf peut-être l'avant-dernière. Si elle n'est pas vérifiée on peut échanger T[i-1] et T[i-1] et alors toutes les conditions seront vérifiées sauf peut-être l'avant-avant-dernière, que l'on peut à nouveau échanger, et ainsi de suite jusqu'à ce que toutes les conditions soient vérifiées.

Cette analyse (ce n'est pas encore une preuve formelle) nous permet de dégager le principe suivant :

On vérifie itérativement que T[i] >= T[i-1] et si ce n'est pas le cas on fait remonter T[i] par échanges successifs à la première place où il sera plus grand que le précédent.

Ce qui se traduit en pseudo-code :

def insertion(T):
    for i in range(1, len(T)):
        j = i
        while (j > 0) and (T[j] < T[j - 1]):
            T[j], T[j - 1] = T[j - 1], T[j]
            j -= 1

L'algorithme insertion, comme l'algorithme sélection, modifie le tableau passé en paramètre.

Pour garantir que T[j - 1] soit toujours valide (il faut que $j-1 \geq 0$), on place en tête de la condition (courant < T[j - 1]) de la ligne 5 la sentinelle (j > 0). Les deux conditions étant liées par un and, python (et tout autre langage de programmation) n'évaluera la seconde condition que si la première est vérifiée (un and ne peut être vrai que si les deux conditions sont vraies. Si la première condition est fausse, il est impossible que le and soit vrai il est donc inutile de vérifier la seconde condition).

À retenir

La technique des sentinelles est très pratique, cela vaut le coup de la connaître.

Fonctionnement

Tout comme pour l'algorithme de tri par sélection, on vérifie que l'algorithme fonctionne pour :

un petit tableau trié : [1, 2, 3]
un petit tableau non trié où le plus petit est en dernière place : [3, 2, 1]

Preuve

Le principe de programmation du tri par insertion est correct puisque est_trie est prouvé. Mais il faut vérifier qu'il est bien mis en œuvre dans l'algorithme.

On a ici deux boucles imbriquée (lignes 2 et 5), il nous faut donc a priori deux invariants de boucles, le second (du while) nous servant à prouver le premier (du for)

Comme l'algorithme du tri par insertion mime l'algorithme de reconnaissance, le premier invariant, celui de la boucle for de la ligne 2 va être le même :

Invariant de boucle

À la fin d'un itération de la boucle for de la ligne 2, les $i + 1$ premiers éléments du tableau sont triés.

Pour prouver cet invariant, il nous faut comprendre ce que fait la boucle while de la ligne 5, c'est à dire lui trouver un invariant.

Invariant de la boucle while

Chaque itération de la boucle while va échanger les éléments placées en $j-1$ et $j$ et décrémenter $j$ jusqu'à ce que soit $j=0$ soit $T[j-1] \leq T[j]$. On a donc l'invariant :

A la fin de chaque itération de la boucle while $T[j] \leq T[j+1]$ si $j <i$

preuve

Cet invariant est clairement vérifié.

On peut donc maintenant démontrer l'invariant de la boucle for :

Invariant de la boucle for

A la fin d'un itération de la boucle for de la ligne 2, les $i + 1$ premiers éléments du tableau sont triés.

preuve

On a $i = 1$ pour la première itération donc à l'issue de la boucle while :

soit $j=i=1$ et $T[0] \leq T[1]$ (car la boucle s'est arrêtée)
soit $j=0$ et $T[0] \leq T[1]$ (invariant de boucle)

Dans les 2 cas, les 2 premiers éléments de $T$ sont triées. L'initialisation de l'invariant est Ok.

On suppose l'invariant vrai à la fin de la $i-1$ ème boucle et on regarde à la fin de la $i$ boucle.

La $i$ ème itération de la boucle for (ligne 2), a fonctionné ainsi :

ligne 3 : on a : T[:i+1] = T[:i] + [T[j]] ($j = i$)
à la sortie de la boucle while, en notant T le tableau avant la boucle while et T' le tableau en fin de while, on a :
1. T'[:i+1] = T[:j] + [T[j]] + T[j:i]
2. T[:j] trié (invariant de la boucle for) et T[j] >= T[j-1] (car on est sorti de la boucle while)
3. T[j:i] trié (invariant de la boucle for) et T[j] < T[j+1] (invariant de la boucle while)

Les constatations précédentes nous montrent que $T'[:i+1]$ est trié, ce qui termine la preuve de l'invariant de la boucle for.

On conclut la preuve de l'algorithme insertion en constatant que l'invariant de la boucle for est vrai en sortie de boucle où $i=n-1$ : les $n$ premier éléments de $T$ sont triés.

Complexités

Ligne à ligne :

appel de fonction : $\mathcal{O}(1)$
$n-1$ itérations, avec $n$ la taille du tableau
affectation d'une variable et récupération d'un élément d'un tableau : $\mathcal{O}(1)$
affectation d'une variable : $\mathcal{O}(1)$
$K_i$ itérations ($K_i$ inconnu) et deux tests en $\mathcal{O}(1)$ pour chaque itération
affectation d'une variable et récupération d'un élément d'un tableau : $\mathcal{O}(1)$
une soustraction et une affectation : $\mathcal{O}(1)$
affectation d'une variable et récupération d'un élément d'un tableau : $\mathcal{O}(1)$

Comme $K_i$ n'est pas constant pour chaque itération de la boucle for il faut regarder les valeurs extrêmes que peut prendre $K$ :

si le tableau est déjà trié : on ne rentre jamais dans la boucle while : $K = 0$ pour chaque itération.
si le tableau est trié à l'envers : pour la $i$-ème itération de la boucle for, on aura $K=i$. C'est de plus le maximum théorique possible ($j=i$ initialement et j décroît de 1 à chaque itération de la boucle while).

On a donc 2 cas extrêmes pour le calcul :

$K_i = 0$ à chaque itération et on peut considérer que $K_i = K=0$ pour tout $i$ dans le cas le plus favorable
$K_i$ croit de $1$ à $n-1$ à chaque itération : la règle de croissance nous indique qu'on peut considérer que $K_i = K=n-1$ pour tout $i$ dans le cas le moins favorable

Ce qui donne une complexité de :

$$ \begin{array}{lcl} C(n) & = & \mathcal{O}(1) + \\ && (n-1) \cdot (\\ && \mathcal{O}(1) + \\ && \mathcal{O}(1) + \\ && K \cdot (\mathcal{O}(1) + \\ && \mathcal{O}(1) + \\ && \mathcal{O}(1)) + \\ && \mathcal{O}(1)) \\ & = & \mathcal{O}(1) + (n-1) \cdot (\mathcal{O}(1) + K \cdot (\mathcal{O}(1))\\ & = & \mathcal{O}(n \cdot (K + 1)) \\ & = & \mathcal{O}(K \cdot n) \\ \end{array} $$

La complexité de l'algorithme insertion est ($n$ est la taille du tableau passé en entrée) :

la complexité min est atteinte pour $K=0$, c'est à dire lorsque le tableau est déjà trié, et vaut $\mathcal{O}(n)$
la complexité (max) est atteinte pour $K=n-1$, c'est à dire lorsque le tableau est trié par ordre décroissant, et vaut $\mathcal{O}(n^2)$

La complexité min est différente de la complexité maximale. On va donc calculer la complexité en moyenne pour connaître la complexité pour des données standard. Pour savoir ce que veut dire standard, il faut déterminer le modèle de données : prenons le équiprobable.

Cela signifie que pour chaque itération $i$ :

T[i] sera bien placé pour une proportion de $\frac{1}{i + 1}$ tableaux et on aura $K_i = \mathcal{O}(1)$ pour ceux-ci.
T[i] devra être positionné en $i-1$ pour une proportion de $\frac{1}{i + 1}$ tableaux, et on aura $K_i = 2\cdot\mathcal{O}(1)$ pour ceux-ci.
...
T[i] devra être positionné en $i-j$ pour une proportion de $\frac{1}{i + 1}$ tableaux, et on aura $K_i = j\cdot\mathcal{O}(1)$ pour ceux-ci.
...
T[i] devra être positionné en $0$ pour une proportion de $\frac{1}{i + 1}$ tableaux, et on aura $K_i = i\cdot\mathcal{O}(1)$ pour ceux-ci.

De façon intuitive

Si les données sont équiprobables, la boucle while remontera en moyenne de $\frac{i}{2}$ cases chaque T[i]. Le nombre moyen d'itérations de $K_i$ sera égal à $\widehat{K_i} = \frac{i}{2}$

de façon formelle

On calcule l'espérance $\widehat{K_i}$ de $K_i$ en sommant le nombre fois la probabilité pour chaque cas, ce qui donne le calcul :

$$ \begin{array}{lcl} \widehat{K_i} &=& \sum_{j=0}^{i}(\frac{1}{i+1}\cdot j)\\ &=& \frac{1}{i+1}\cdot \frac{(i+1)\cdot i}{2})\\ &=& \frac{i}{2}\\ \end{array} $$

On en conclut que le nombre moyen d'itérations dans la boucle while, $\widehat{K_i}$, va croitre de 0 à $\frac{n}{2}$ et on peut utiliser la la règle de croissance pour considérer que la complexité moyenne du tri par insertion vaut $C_\text{moyenne}(n) = \widehat{K} \cdot n$ avec $\widehat{K} = \frac{n}{2}$. On en conclut que la complexité moyenne vaut : $C_\text{moyenne}(n) = \mathcal{O}(n^2)$

La complexité en moyenne de l'algorithme insertion est $\mathcal{O}(n^2)$ où $n$ est la taille du tableau passé en entrée.

Le cas le meilleur arrive très rarement par rapport au cas le pire (parmi les $n!$ ordres possibles, il y en a très peu qui sont presque triés).

Si l'on change le modèle de données et que l'on considère des tableaux presque triées, la complexité en moyenne va être de l'ordre de la complexité minimale, à savoir : $\mathcal{O}(n)$

On utilise le tri par insertion lorsque nos données seront presque toujours déjà triées ou très peu en désordre.

Ce calcul de complexité nous permet d'utiliser la règle suivante, qui va se révéler très utile :

Soit $A$ un ensemble de $n$ nombres aléatoires, et $x$ un nombre également aléatoire. Pour tout $ y \in A$, il y a 50% de chances que $x \leq y$. Il y a donc en moyenne $\frac{n}{2}$ éléments de $A$ qui sont plus grand que $x$.

Optimisation

Une implémentation courante du tri par insertion est la suivante :

def insertion(T):
    for i in range(1, len(T)):
        courant = T[i]
        j = i
        while (j > 0) and (courant < T[j - 1]):
            T[j] = T[j - 1]
            j -= 1
        T[j] = courant

Remarquez qu'elle ne fait pas d'échange à chaque fois. Elle se contente de faire de la place pour l'élément que l'on va insérer en décalant uniquement les valeurs du tableau. Une fois la place trouvée, il suffit de placer l'élément une fois. Finaud, non ?