Nombre de comparaisons

Rappelons que le temps nécessaire à l'exécution d'un programme est lié au nombre d'opérations élémentaires effectuées par ce programme. Les opérations élémentaires: comparaisons, affectations, additions, accès à un élément de liste...

Pour simplifier ce travail de décompte des opérations, nous nous limitons au décompte du nombre de comparaisons (c'est en général un bon choix pour avoir une bonne idée de "l'ordre de grandeur" du nombre d'opérations dans un tri).

Exercice

On reprend le code de la recherche de l'indice du maximum rechercheIndiceMax(tab, debut, fin):

Rappel du code de rechercheIndiceMax(tab, debut, fin)

def rechercheIndiceMax(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur maximale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 1,3)
    3
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 0,3)
    0
    """
    m = tab[debut] # sera le max de tab[debut..fin]
    indice = debut # sera l'indice du max de tab[debut..fin]
    for i in range(debut+1, fin+1):
        if tab[i] > m:
            m = tab[i]
            indice = i
    return indice

Quel est le nombre de comparaisons effectuées lors d'un appel rechercheIndiceMax(tab, debut, fin)?

Remarque

On répondra bien entendu en fonction de debut et fin.

Solution

On effectue une comparaison pour chaque valeur de i comprise entre debut+1 et fin (bornes comprises). On effectue donc fin-debut comparaisons.

Exercice

On reprend le code du tri (en place) par sélection du max (rappelé ci-dessous):

Rappel du code du tri sur place par sélection du maximum

def rechercheIndiceMax(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur maximale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 1,3)
    3
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 0,3)
    0
    """
    m = tab[debut] # sera le max de tab[debut..fin]
    indice = debut # sera l'indice du max de tab[debut..fin]
    for i in range(debut+1, fin+1):
        if tab[i] > m:
            m = tab[i]
            indice = i
    return indice




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

    Modifie tab en triant ses éléments en ordre croissant.
    """
    for i in range(0, len(tab)-1):
        im = rechercheIndiceMax(tab, 0, len(tab)-1-i)
        tab[len(tab)-1-i], tab[im] = tab[im], tab[len(tab)-1-i]

Quel est le nombre de comparaisons effectuées lors d'un appel à la fonction triSelection?

Remarque

On répondra bien entenu en fonction de la longueur n de la liste tab donnée en argument.

Solution

On note n = len(tab).

Les comparaisons sont faites lors des appels rechercheIndiceMax(tab, 0, len(tab)-1-i). Le nombre de comparaisons effectuées est n-1-i.

i prend successivement les valeurs 0, 1, 2, ..., n-2.

Le nombre total de comparaisons est donc la somme: $S = (n-1)+(n-2)+(n-3)+...+1$.

Cette somme a pour valeur $S = \frac{1}{2} n(n-1)$.

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.

Remarque

Rappelons que le tri par insertion présentait un nombre de comparaisons "au mieux" bien meilleur que le cas "au pire" (fonction affine en n versus fonction du second degré en n).

On voit ici que les cas "au pire" et "au mieux" sont les mêmes pour le tri par sélection.