Analyse du tri par insertion — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Analyse du tri par insertion

Complexité algorithmique

Énoncé

L'algorithme de tri par insertion est implémenté ci-dessous :

def tri_insertion(L):
    for i in range(1, len(L)):
        cle = L[i]
        j = i - 1
        while j >= 0 and L[j] > cle:
            L[j+1] = L[j]
            j -= 1
        L[j+1] = cle
    return L

Déterminer la complexité temporelle dans le meilleur des cas, le pire des cas, et en moyenne.

Corrigé

Soit $n = len (L)$ .

Meilleur des cas : La liste est déjà triée par ordre croissant. La condition du test L[j] > cle est systématiquement fausse. La boucle interne while ne s'exécute jamais. La boucle externe fait $n - 1$ passages en effectuant un nombre constant d'opérations à chaque étape. La complexité est linéaire : $Θ (n)$ .

Pire des cas : La liste est initialement triée dans l'ordre inverse (décroissant). À chaque étape $i$ , la variable cle est comparée à tous les éléments précédents qui lui sont supérieurs. La boucle interne s'exécute exactement $i$ fois. Le nombre total d'itérations internes vaut : $i = 1 \sum n - 1 i = \frac{n ( n - 1 )}{2}$ La complexité est quadratique : $Θ (n^{2})$ .

Cas moyen : Pour une permutation aléatoire, chaque élément est inséré à mi-chemin en moyenne, ce qui fait $i /2$ itérations de la boucle interne. De plus, le nombre de déplacements correspond au nombre moyen d'inversions de la liste, qui vaut $\frac{n ( n - 1 )}{4}$ . La complexité en moyenne reste quadratique : $Θ (n^{2})$ .