Tri par insertion☘

Nous pouvons maintenant utiliser la fonction d'insertion précédemment définie pour programmer un tri de liste.

Le tri☘

Utiliser ce qui a été défini dans la page précédente (rappelé ci-dessous)

Rappel du code de la page précédente

def rechercheIndicePivot(tab, valeur):
    """
    tab -- liste d'entiers, précondition: tab triée en ordre croissant
    valeur -- entier

    renvoie le plus petit indice i tel que tab[i] >= valeur
    et renvoie len(atb) si un tel indice n'existe pas.
    """
    for indice, element in enumerate(tab):
        if element >= valeur: return indice
    return len(tab)



def insertion(tab, valeur):
    """
    tab -- liste d'entiers, précondition: liste est triée en ordre croissant
    valeur -- entier

    renvoie une liste dont les éléments sont les éléments de tab et valeur, la liste
    renvoyée est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    """
    indice_pivot = rechercheIndicePivot(tab, valeur)
    return [tab[k] for k in range(indice_pivot)] + [valeur] + [tab[k] for k in range(indice_pivot, len(tab))]

pour écrire un corps possible pour la fonction suivante:

def triInsertion(tab):
    """
    tab -- liste d'entiers

    renvoie une liste de même contenu que tab, mais triée en ordre croissant.
    """

Principe (à connaître!)

On utilise le principe, exposé en introduction, du joueur qui tire ses cartes une à une:

Dans une liste vide, on insère tab[0].
Dans la liste ainsi obtenue, on insère tab[1].
Dans la liste obtenue, on insère tab[2].
...etc

Solution

Un code possible:

def rechercheIndicePivot(tab, valeur):
    """
    tab -- liste d'entiers, 
    précondition: tab triée en ordre croissant
    valeur -- entier

    renvoie le plus petit indice i tel que tab[i] >= valeur
    et renvoie len(tab) si un tel indice n'existe pas.
    """
    for indice, element in enumerate(tab):
        if element >= valeur: return indice
    return len(tab)



def insertion(tab, valeur):
    """
    tab -- liste d'entiers, 
    précondition: liste est triée en ordre croissant
    valeur -- entier

    renvoie une liste dont les éléments 
    sont les éléments de tab et valeur, la liste
    renvoyée est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    """
    indice_pivot = rechercheIndicePivot(tab, valeur)
    return [tab[k] for k in range(indice_pivot)] + [valeur] + [tab[k] for k in range(indice_pivot, len(tab))]




def triInsertion(tab):
    """
    tab -- liste d'entiers

    renvoie une liste de même contenu que tab, 
    mais triée en ordre croissant.

    >>> triInsertion([3, 1, 9, 42, 2, 5])
    [1, 2, 3, 5, 9, 42]
    >>> triInsertion([])
    []
    >>> triInsertion([666, 42, 1789, 777])
    [42, 666, 777, 1789]
    """
    liste = []
    for k in range(0, len(tab)):
        liste = insertion(liste, tab[k])
    return liste

Une preuve☘

Note

Cet exercice consiste à démontrer que la fonction de l'exercice précédent trie bien la liste en ordre croissant.
Pour cela, on va utiliser un invariant de boucle. Nous reviendrons sur cette notion d'invariant de boucle de façon plus systématique plus tard dans l'année.

Dans la boucle du code de l'exercice précédent:

liste = []
for k in range(0, len(tab)):
    #
    liste = insertion(liste, tab[k])
    ##

Soit i un entier entre 0 et len(tab)-1;

Lorsque k = i, que contient liste à la ligne marquée d'un # puis à la ligne marquéé ## ?
Quelle est la longueur de liste lorsque k = i à la ligne marquée d'un # puis à la ligne marquéé ## ?

Réponse

Avant la boucle, liste est intialisée à [].
k = 0
A l'entrée dans la boucle (ligne marquée d'un #) pour k = 0, liste est donc vide.
On exécute alors le corps de boucle liste = insertion(liste, tab[0]). A la fin du passage dans la boucle (ligne ##), liste contient donc un seul élément: tab[0].
k = 1
En début de boucle pour k = 1, liste contient donc un seul élément: tab[0].
Puis on exécute le corps de boucle liste = insertion(liste, tab[1]).
En fin de passage dans la boucle, liste contient donc les éléments tab[0] et tab[1] triés en ordre croissant.
k = 2
En début de boucle pour k = 2, liste contient tab[0] et tab[1].
Puis on exécute le corps de boucle liste = insertion(liste, tab[2]).
En fin de passage dans la boucle, liste contient donc les éléments tab[0], tab[1], tab[2] triés en ordre croissant.
...
k = i
Si en entrée de boucle avec k=i, liste contient les éléments de tab[0..(i-1)] triés en ordre croissant, alors après exécution du corps de boucle, qui consiste à insérer tab[i] à sa place, liste contiendra les éléments de tab[0..i], triés en ordre croissant, en fin de passage dans la boucle.
Et en entrée de passage suivant, k = i_suivant = i+1, on aura à nouveau la propriété "liste contient les éléments de tab[0..(i_suivant-1)] triés en ordre croissant".

Cette propriété, conservée après exécution du corps de boucle, est appelée "invariant de boucle".

Nombre d'éléments

On a montré que la propriété "liste contient les éléments de tab[0..(i-1)] triés en ordre croissant" était satisfaite à chaque début de passage dans le corps de boucle (pour k = i).
En début de passage dans la boucle (pour k = i), liste contient donc i éléments. Elle en contient i+1 en fin de passage dans la boucle.

Utilisation de l'invariant

En sortie de boucle, c'est à dire après exécution du corps de boucle pour k = len(tab)-1, liste contient k+1 = len(tab)-1+1 = len(tab) éléments. liste contient donc tous les éléments de tab, triés en ordre croissant. On a donc bien obtenu une liste contenant les éléments de la liste donnée en entrée, mais ordonnés en ordre croissant.

La complexité☘

Quel est le nombre de comparaisons lors d'un appel à la fonction triInsertion précédente?

Remarque

On répondra, bien sûr, en fonction du nombre n d'éléments de la liste passée en argument.
On répondra en encadrant le nombre de comparaisons par le nombre minimal de comparaisons effectuées et le nombre maximal de comparaisons effectuées.

Somme des n premiers entiers naturels

Pour un entier n, la somme 0 + 1 + 2 + ... + (n-1) est égale à $\frac{1}{2}n(n-1)$ .

On retrouve ce résultat avec "l'astuce" ci-dessous qui consiste à ajouter cette somme avec elle-même:

	S	=	0	+	1	+	2	+	...	+	(n-3)	+	(n-2)	+	(n-1)
+	S	=	(n-1)	+	(n-2)	+	(n-3)	+	...	+	2	+	1	+	0
	2S	=	(n-1)	+	(n-1)	+	(n-1)	+	...	+	(n-1)	+	(n-1)	+	(n-1)

On remarque que chaque "colonne" a nécessairement la même somme puisque l'unité ajoutée dans la ligne du haut pour passer au terme suivant est enlevée dans la ligne du bas.

Ainsi: $2S = n\times (n-1)$ , d'où la formule.

Réponse

On note n la longueur de la liste passée en argument.

Lors d'un passage dans la boucle:

for k in range(0, len(tab)):
    liste = insertion(liste, tab[k])

on appelle insertion sur une liste qui a pour longueur k.

Lorsque k = 0, insertion n'effectue aucune comparaison.
Pour k > 0, insertion effectue entre 1 et k comparaisons (effectuées dans rechercheIndicePivot).

Si on cumule:

le nombre minimum de comparaisons est 0 + 1 + 1 + ... + 1 = n-1.
le nombre maximum de comparaisons est 0 + 1 + 2 + ... + (n-1) $= \frac{1}{2}n(n-1)$ .

Expliciter des cas extrêmes☘

Dans l'exercice précédent, on a établi que le nombre de comparaisons était au mieux de n-1 (où n est la longueur de la liste passée en argument) et au pire de $\frac{1}{2}n(n-1)$ .

Donner pour chacun de ces deux cas extrêmes, un exemple de liste réalisant ce nombre de comparaisons.

au mieux

Vérifiez que pour une liste constante, le nombre de comparaisons est n-1 (n désignant le nombre d'éléments de la liste).

Vous pouvez également vérifier que le nombre de comparaisons sera n-1 pour une liste de n valeurs distinctes déjà triée en ordre décroissant.

au pire

Vérifiez qu'une liste de n valeurs distinctes et déjà triée en ordre croissant donnera le nombre de comparaisons le pire.

Vérification expérimentale

On peut faire quelques tests en installant des compteurs (ligne 12 de la première fonction: on ajoute 1 à un compteur à chaque fois que la ligne if element >= valeur va être exécutée).

compteur = {'comparaison': 0}

def rechercheIndicePivot(tab, valeur):
    """
    tab -- liste d'entiers, précondition: tab triée en ordre croissant
    valeur -- entier

    renvoie le plus petit indice i tel que tab[i] >= valeur
    et renvoie len(atb) si un tel indice n'existe pas.
    """
    for indice, element in enumerate(tab):
        compteur['comparaison'] += 1
        if element >= valeur: 
            return indice
    return len(tab)



def insertion(tab, valeur):
    """
    tab -- liste d'entiers, précondition: liste est triée en ordre croissant
    valeur -- entier

    renvoie une liste dont les éléments sont les éléments de tab et valeur, la liste
    renvoyée est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    """
    indice_pivot = rechercheIndicePivot(tab, valeur)
    return [tab[k] for k in range(indice_pivot)] + [valeur] + [tab[k] for k in range(indice_pivot, len(tab))]



def triInsertion(tab):
    """
    tab -- liste d'entiers

    renvoie une liste de même contenu que tab, mais triée en ordre croissant.
    """
    liste = []
    for k in range(0, len(tab)):
        liste = insertion(liste, tab[k])
    return liste



#### TESTS 
n = 6
A = [  k for k in range(n)]
triInsertion(A)
print(f"Nombre de comparaisons pour la liste testée: {compteur['comparaison']}.")
print(f"n-1 = {n-1}.")
print(f"1/2*n*(n-1) = {1/2*n*(n-1)}.")