C18.3 : Tri par insertion

L'algorithme de tri par insertion est un algorithme classique qui permettent de trier une liste.

Principe

Dans cet algorithme, il s'agit de prendre les valeurs de la liste les unes après les autres et de les insérer de façon à ce qu'elles forment une portion triée de liste.

Lien : Visualisation du principe du tri par insertion

Algorithme

🖊️ Repérer les actions qui sont répétées.

🖥️ Proposer une fonction qui prend une liste en paramètre et modifie cette liste pour qu'à la fin de l'exécution de la fonction la liste soit triée par ordre croissant.

🖥️ Compléter avec le programme principal qui permet de tester la fonction avec une liste de 20 nombres entiers choisis aléatoirement entre 0 et 99.

Afficher la correction 
from random import randint

def tri_insertion(L):
    '''
    Tri la liste L du plus grand au plus petit
    param L: (list) Liste de nombres entiers
    effets de bord : le paramètre L est modifié
    '''
    for i in range(1, len(L)):
        elt = L[i]
        p = i-1
        while p >= 0 and elt > L[p]:
            L[p+1] = L[p]
            p = p - 1
        L[p+1] = elt


# -----Programme principal-----
liste = [randint(0,99) for _ in range(20)]
print(liste)
tri_insertion(liste)
print(liste)

Analyse de l'algorithme

Terminaison de l'algorithme

🖊️ Démontrer la terminaison de l'algorithme.

Afficher la correction

■ Pour la boucle for

La boucle for se termine nécessairement

■ Pour la boucle while

Le variant convergeant de boucle est p.

En effet :

  • - Tout d'abord, notons que p commence à i-1 ;
  • - Par ailleurs, dans la boucle, p diminue de 1 à chaque itération donc les valeurs de p forment une suite d'entiers strictement décroissante ;
  • - Or lorsque la valeur de p n'est plus positive ou nulle, on sort de la boucle ;
  • - Donc on sort nécessairement de la boucle.

Correction de l'algorithme

🖊️ Proposer un invariant pour chacune des deux boucles.

Afficher la correction

Pour démontrer la correction de l'algorithme, on cherche un invariant de boucle, c'est à dire une propriété qui reste vraie à chaque itération dans la boucle.

• Pour la boucle for, l'invariant de boucle est : « La partie de la liste de 0 à i est triée ».

• Pour la boucle while, de façon simplifiée, l'invariant de boucle est la proposition suivante : « La partie de la liste de 0 à p-1 et la partie de la liste de p+1 à i sont triées ».
Remarque : il faut un énoncé plus rigoureux pour les cas limites.

Coût

🖊️ Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?

Afficher la correction

L'algorithme fait le moins de comparaison lorsque la boucle est déjà triée.

Si on note n la longueur de la liste à trier, dans dans ce cas il fait n-1 comparaisons.

Dans ce cas, le coût de l'algorithme est proportionnel à n, on dit que le coût est linéaire.

🖊️ Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?

Afficher la correction

L'algorithme fait le plus de boucle lorsque la liste est totalement inversée par rapport à l'ordre souhaité.

Si on note n la longueur de la liste à trier, dans ce cas il fait 1 + 2 + 3 + ... + (n-1) = (n-1)×n/2.

Remarque : 1 + 2 + 3 + ... + k = k×(k+1)/2

Dans ce cas, le coût de l'algorithme est proportionnel à n², on dit que le coût est quadratique.

Pour aller plus loin

Lien : Algorithmes de tri

Lien : Algorithmes de tri animés