Algorithmes de tri (1) : tri par insertion

Préambule

Pourquoi étudier des algorithmes de tri ?
Autant ne pas le cacher, ces algorithmes sont déjà implémentés (quelque soit le langage) dans des fonctions très performantes.

En Python, on utilise la fonction sort()

In [1]:
tab = [4, 8, 1, 2, 6]
tab.sort()
In [2]:
tab
Out[2]:
[1, 2, 4, 6, 8]

Le meilleur de nos futurs algorithmes de tri sera moins efficace que celui de cette fonction sort()...
Malgré cela, il est essentiel de se confronter à l'élaboration manuelle d'un algorithme de tri.
Le tri par insertion est le premier des deux algorithmes de tri que nous allons étudier (nous étudierons aussi le tri par sélection).
Ces deux algorithmes ont pour particularité de :

  • ne pas nécessiter la création d'une nouvelle liste. Ils modifient la liste à trier sur place.
  • ne pas faire intervenir de fonctions complexes (comme la recherche d'un minimum par exemple)

Tri par insertion (version la plus intuitive)

Considérons la liste [7, 5, 2, 8, 1, 4]
Voici le fonctionnement de l'algorithme :

Explications :

  • on traite successivement toutes les valeurs à trier, en commençant par celle en deuxième position.
  • Traitement : tant que la valeur à traiter est inférieure à celle située à sa gauche, on échange ces deux valeurs.

 Codage de l'algorithme

Complétez l'algorithme ci-dessous

In [3]:
def tri(l) :
    for k in range(1, len(l)):
        i = k
        while  i>0 and l[i-1] > l[i] :
            l[i], l[i-1] = l[i-1], l[i]
            i = i -1

Vérification :

In [4]:
a = [7, 5, 2, 8, 1, 4]
tri(a)
print(a)

[1, 2, 4, 5, 7, 8]

Tri par insertion (version optimisée)

Observez l'animation ci-dessous et comparer avec la version initiale.

 Codage de l'algorithme

Complétez l'algorithme ci-dessous

In [7]:
def tri(l) :
    for k in range(1,len(l)):
        cle = l[k]
        i = k-1
        while  i>=0 and l[i] > cle :
            l[i+1] = l[i]
            i = i -1
        l[i+1] = cle

Vérification :

In [8]:
a = [7, 5, 2, 8, 1, 4]
tri(a)
print(a)

[1, 2, 4, 5, 7, 8]

 Complexité de l'algorithme

Pour pouvoir utiliser la fonction %timeit, nous allons modifier légèrement notre algorithme de tri : comme la fonction %timeit effectue un grand nombre d'appel à la fonction tri(), la liste serait triée dès le premier appel et les autres appels essaieraient donc de tri une liste déjà triée.

In [1]:
def tri(L) :
    l = list(L) # pour ne pas modifier la liste passée en argument.
    for k ...
In [2]:
a = [k for k in range(100,0,-1)] #on se place dans le pire des cas : une liste triée dans l'ordre décroissant
In [6]:
b = [k for k in range(200,0,-1)] #on se place dans le pire des cas : une liste triée dans l'ordre décroissant
In [4]:
%timeit tri(a)

547 µs ± 4.97 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [7]:
%timeit tri(b)

2.16 ms ± 8.67 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

En comparant les temps de tri des listes a et b, que pouvez-vous supposer sur la complexité du tri par insertion ?

In [ ]:

Démonstration

Dénombrons le nombre d'opérations dans le pire des cas, pour une liste de taille $n$.

  • boucle for : elle s'exécute $n-1$ fois.
  • boucle while : dans le pire des cas, elle exécute d'abord 1 opération, puis 2, puis 3... jusqu'à $n-1$. Or $$1+2+3+\dots+n-1=\dfrac{n \times (n-1)}{2}$$

Si la liste est déjà triée, on ne rentre jamais dans la boucle while : le nombre d'opérations est dans ce cas égal à $n-1$, ce qui caractérise une complexité linéaire.

Résumé de la complexité

  • dans le meilleur des cas (liste déjà triée) : complexité linéaire
  • dans le pire des cas (liste triée dans l'ordre décroissant) : complexité quadratique

 Preuve de la terminaison de l'algorithme

Est-on sûr que notre algorithme va s'arrêter ?
À l'observation du programme, constitué de deux boucles for imbriquées, il n'y a pas d'ambiguïté : on ne peut pas rentrer dans une boucle infinie. Le programme s'arrête forcément au bout de d'un nombre fixe d'opérations. D'après nos calculs sur la complexité, ce nombre de tours de boucles est égal à $$\dfrac{n \times (n-1)}{2}$$

Ceci prouve que l'algorithme se terminera.

Il existe une notion théorique appelée variant de boucle. C'est une valeur entière positive qui décroit à chaque itération du programme. Lorsque cette valeur vaut 0, cela signifie que le programme s'arrête. Ici, le variant de boucle pourrait être la valeur i de la boucle while.

 Preuve de la correction de l'algorithme

Les preuves de correction sont des preuves théoriques. La preuve ici s'appuie sur le concept mathématique de récurrence. Principe du raisonnement par récurrence : une propriété $P(n)$ est vraie si :

  • $P(0)$ (par exemple) est vraie
  • Pour tout entier naturel $n$, si $P(n)$ est vraie alors $P(n+1)$ est vraie.

Ici, la propriété serait : « Quand $k$ varie entre 0 et longueur(liste) -1, la sous-liste de longueur $k$ est triée dans l'ordre croissant.» On appelle cette propriété un invariant de boucle (sous-entendu : elle est vraie pour chaque boucle)

  • quand $k$ vaut 0, on place le minimum de la liste en l[0], la sous-liste l[0] est donc triée.
  • si la sous-liste de $k$ éléments est triée, l'algorithme rajoute en dernière position de la liste le minimum de la sous-liste restante, dont tous les éléments sont supérieurs au maximum de la sous-liste de $k$ éléments. La sous-liste de $k+1$ éléments est donc aussi triée.
In [ ]: