1NSI : Tri par insertion

Contenus	Capacités Attendues	Commentaires
Tri par Insertion, par Sélection	Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.	La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas.

Tri par Insertion (version la plus intuitive)

Animation

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

Principe de l'Algorithme

• On traite successivement (de gauche à droite) 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.

L'Algorithme en Python

Pour toutes les valeurs, en commençant par la deuxième :

• Tant qu'on trouve à gauche une valeur supérieure (à la valeur courante), et qu'on n'est pas encore parvenu à la première valeur :

  • on échange ces deux valeurs
  • on se décale d'un cran vers la gauche : la valeur courante est maintenant celle de gauche

  Tri par insertion (version simple)

  def tri_insertion1(l:list):
      '''trie en place la liste l donnée en paramètre'''
      for i in range(1, len(l)):                   #(1)
          k = i                                    #(2)
          while k > 0 and l[k-1] > l[k] :          #(3)
              l[k], l[k-1] = l[k-1], l[k]          #(4)
              k = k - 1                            #(5)
  

  1. On commence à 1 et non pas à 0.
  2. On «duplique» la variable i en une variable k.
     On se positionne sur l'élément d'indice k. On va faire «reculer» cet élément tant que c'est possible. On ne touche pas à i.
  3. Tant qu'on n'est pas revenu au début de la liste et qu'il y a une valeur plus grande à gauche.
  4. On échange de place avec l'élément précédent.
  5. Notre élément est maintenant à l'indice k - 1.
     La boucle peut continuer.

Utilisation

>>> maliste = [7, 5, 2, 8, 1, 4]
>>> tri_insertion1(maliste)
>>> maliste
[1, 2, 4, 5, 7, 8]

Tri par Insertion (version optimisée)

Animation

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

Principe de l'Algorithme

• Au lieu d'effectuer un échange avec la valeur précédente à chaque fois qu'elle est supérieure, on va décaler vers la droite toutes les valeurs :
  • situées à gauche de la valeur courante, et
  • qui sont supérieures à notre valeur courante
• On insère ensuite notre valeur courante, directement à sa position «la plus à gauche possible»

L'Algorithme en Python

Tri par insertion (version optimisée)

def tri_insertion2(l:list):
    '''trie en place la liste l donnée en paramètre'''
    for i in range(1, len(l)):           # (1)
        cle = l[i]                       # (2)
        k = i - 1                        # (3)
        while k >= 0 and l[k] > cle :    # (4)
            l[k + 1] = l[k]              # (5)
            k = k -1                     # (6)
        l[k + 1] = cle                   # (7)

1. On démarre à la deuxième valeur.
2. On stocke dans une variable cle notre valeur courante
3. On démarre l'étude des valeurs à gauche de notre valeur courante
4. Tant qu'on trouve une valeur supérieure à notre valeur courante, et qu'on n'est pas revenus au début de la liste.
5. On décale cette valeur de un rang vers la droite.
6. On se repositionne sur la valeur à gauche de notre valeur courante.
7. On s'est arrêté quand la valeur n'était pas supérieure : on insère notre valeur courante juste à droite de notre position d'arrêt.

Utilisation

>>> maliste = [7, 5, 2, 8, 1, 4]
>>> tri_insertion2(maliste)
>>> maliste
[1, 2, 4, 5, 7, 8]

Terminaison de l'Algorithme

Est-on sûr que notre algorithme va s'arrêter (un jour) ?
Le programme est constitué d'une boucle for et d'une boucle while imbriquées.

• En ce qui concerne la boucle for, le nombre v=i est un variant de boucle, comme usuellement pour toutes les boucles for (dont l'indice augmente, ici i)
• Nous allons donc nous concentrer sur la boucle while (pour chacune des valeurs i).

Observons donc ses conditions de sortie :

 while  k >= 0 and l[k] > cle :

Montrons que \(v = k+1\) est un variant de boucle (pour la boucle while) :

• \(v\) est un nombre entier
• En entrant dans la boucle while, \(v=(i-1) +1 \geq (1-1)+1 \gt 0\), car \(i\geq 1\)
• \(v\) décroît strictement à chaque itération, d'après la ligne 8 (k=k-1)
• L'inégalité \(v\leq 0 \Leftrightarrow k+1 \leq 0 \Leftrightarrow k \leq -1 \Leftrightarrow k \lt 0\) provoque la sortie de la boucle (car on est sûrs qu'au moins l'une des deux conditions k>=0 et l[k]> cle est fausse - en fait la première condition)

Conclusion: Pour toute valeur de i, la boucle while termine car v est un variant de boucle, donc l'algorithme termine.

Terminaison

L'algorithme du Tri par insertion termine

Correction de l'Algorithme

def tri_insertion2(l:list): # Version Optimisée
    '''trie en place la liste l donnée en paramètre'''
    for i in range(1, len(l)):           # (1)
        cle = l[i]                       # (2)
        k = i - 1                        # (3)
        while k >= 0 and l[k] > cle :    # (4)
            l[k + 1] = l[k]              # (5)
            k = k -1                     # (6)
        l[k + 1] = cle                   # (7)

1. On démarre à la deuxième valeur.
2. On stocke dans une variable cle notre valeur courante
3. On démarre l'étude des valeurs à gauche de notre valeur courante
4. Tant qu'on trouve une valeur supérieure à notre valeur courante, et qu'on n'est pas revenus au début de la liste.
5. On décale cette valeur de un rang vers la droite.
6. On se repositionne sur la valeur à gauche de notre valeur courante.
7. On s'est arrêté quand la valeur n'était pas supérieure : on insère notre valeur courante juste à droite de notre position d'arrêt.

Nous savons maintenant que notre algorithme termine, mais est-on sûr que notre algorithme est correct : autrement dit, l'algorithme va-t-il bien trier notre liste ?

On note n = longueur(liste l) Il s'agit de choisir une propriété \(P\) qui soit un Invariant de Boucle, et qui dépende du (ou des) paramètres du problème/de la boucle. Ici, pour tout entier \(i\) compris entre \(0\) et \(n-1\), on peut choisir :

\(P(i)\) : « Au sortir de la \(i\)-ème itération, la sous-liste (de longueur \(i+1\)) des \(i+1\) premières valeurs est triée dans l'ordre croissant. »

• Initialisation : Après le 1er tour, càd lorsque \(i=1\), on place le minimum de la liste en l[0], quitte à permuter l[0] avec l[1] si besoin : La sous-liste constituée de l[0] et l[1] (contenant \(1+1=2\) valeurs) est donc triée. Donc \(P(1)\) est vraie.
• Hérédité : Si, après la i-ème itération de la boucle for, la sous-liste des \(i+1\) premiers éléments est triée (des positions 0 à i), càd si \(P(i)\) est vraie, Alors, après une itération de plus de la boucle for (càd après la (i+1)-ième itération) l'algorithme insère à sa bonne place (quelque part entre les positions 0 et i+1) la nouvelle cle (=l[i]). Finalement, après la i+1-ième itération, la sous-liste des \(i+2\) premiers éléments est donc aussi triée (constituée de l[0], de l[1], .. et de l[i+1]), càd que \(P(i+1)\) est vraie
• Terminaison : Après la dernière (la n-1-ième) itération de la boucle for, la sous-liste des (n-1)+1 = n valeurs est donc triée, ce qui prouve que l'algorithme est correct (car la liste entière est bien triée)

Complexité de l'Algorithme

Étude Expérimentale

Proposer des mesures expérimentales pour déterminer la complexité du tri par Insertion.

Pour mesurer les temps d'exécution, nous allons utiliser la fonction timeit du module timeit. Avant toute chose, néanmoins, il va nous falloir modifier légèrement notre algorithme de tri. En effet, la fonction timeit fait un grand nombre d'appels (1000000 de fois, par défaut) à la fonction tri_insertion() (pour ensuite en faire la moyenne) : la liste serait donc triée dès le premier appel et les autres appels essaieraient donc de tri une liste déjà triée.

def tri_insertion(L) :
    l = list(L) # pour ne pas modifier la liste passée en argument.
    for k ...

Nous allons fabriquer deux listes la et lb de taille \(100\) et \(200\) :

# Définir deux listes de nombres, dont la deuxième 'lb' est deux fois plus longue que la première 'la'
# on se place dans le pire des cas : chaque liste à trier est initialement dans l'ordre décroissant
la = [k for k in range(100,0,-1)]
lb = [k for k in range(200,0,-1)]

La mesure du temps moyen de tri pour ces deux listes est donnée par la fonction timeit du module timeit :

from timeit import timeit
ta = timeit("tri_insertion(la)", globals=globals(), number=100)  # number = 1000000, par défaut
tb = timeit("tri_insertion(lb)", globals=globals(), number=100)  # number = 1000000, par défaut
print(f"ta = {ta}")
print(f"tb = {tb}")

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

Réponse

Une liste à trier \(2\) fois plus longue prend \(4\) fois plus de temps : l'algorithme semble de complexité quadratique.

TD Matplotlib

En utilisant la librairie Matplotlib, tracer la courbe de la fonction qui :

• A chaque taille \(n\) d'une liste donnée en entrée
• associe le temps mis par la machine pour trier une liste de taille \(n\), mesuré grâce le module time de Python

Corr

from matplotlib import pyplot as plt
import time
from random import randint

def tri_insertion(l:list):
    """trie en place la liste l donnée en paramètre
    et en plus ca fait çà
    """
    for i in range(1, len(l)):
        cle = l[i]
        k = i - 1
        while k >= 0 and l[k] > cle:
            l[k + 1] = l[k]
            k = k -1
        l[k + 1] = cle

def liste_alea(n:int,a:int,b:int)->list:
    return [randint(a,b) for i in range(n)]

def creer_toutes_listes(a:int,b:int)->list:
    l = []
    for i in range(10,210,10):
        l.append(liste_alea(i, a, b))
    return l

def calcul_tous_x(listes):
    x = []
    for l in listes:
        x.append(len(l))
    return x

def calcul_tous_y(listes):
    y = []
    for l in listes:
        start = time.time()
        tri_insertion(l)
        end = time.time()
        temps = end-start
        y.append(temps)
    return y

listes = creer_toutes_listes(20, 50)
x = calcul_tous_x(listes)
y = calcul_tous_y(listes)

plt.suptitle("Complexité du Tri par insertion")
plt.grid(True)
plt.xlabel("n = taille de la liste à trier")
plt.ylabel("C(n) = Complexité en Temps pour trier une liste de taille n")
plt.plot(x,y)

plt.show()

Vous devriez voir quelque chose qui ressemble à ceci :

Calcul du nombre d'opérations

Dénombrons le nombre d'opérations \(C(n)\), dans le pire des cas, pour une liste l de taille \(n\) (=len(l))

• boucle for : (dans tous les cas) 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 :

\[\begin{align} C(n) &= 1+2+3+\dots+n-1 \\ &= \dfrac{n \times (n-1)}{2} \\ &=\dfrac {n^2-n}{2} \\ &=\dfrac{n^2}{2}-\dfrac{n}{2} \end{align} \]

Dans le pire des cas, donc, le nombre \(C(n)\) d'opérations effectuées / le coût \(C(n)\) / la complexité \(C(n)\) est mesurée par un polynôme du second degré en \(n\) dont le terme dominant (de plus haut degré) est \(\dfrac{n^2}{2}\), donc proportionnel au carré de la taille \(n\) des données en entrées, càd proportionnel à \(n^2\), càd en \(O(n^2)\). Ceci démontre que :

Complexité dans le pire des cas

Dans le pire des cas (liste triée dans l'ordre décroissant), le tri par insertion est de complexité quadratique, en \(O(n^2)\)

Dans le meilleur des cas (rare, mais il faut l'envisager) qui correspond ici au cas où 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.

Complexité dans le meilleur des cas

Dans le meilleur des cas (liste déjà triée), le tri par insertion est de complexité linéaire, en \(O(n)\)

Vérification expérimentale

Insérez un compteur c dans votre algorithme pour vérifier le calcul précédent. On pourra renvoyer cette valeur en fin d'algorithme par un return c.

Résumé de la Complexité

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

Références & Notes

• Tri par insertion, Gilles Lassus
• Wikipedia, https://en.wikipedia.org/wiki/Sorting_algorithm