⌨ Spécialité NSI · Numérique et sciences informatiques Première Générale · Chapitre 8

Tris et complexité

Parcours séquentiel d'un tableau et coût linéaire, tri par sélection et tri par insertion, invariant de boucle et terminaison, coût quadratique, comparaison expérimentale des durées.

1. Parcours séquentiel

Propriété · Coût linéaire

Rechercher une valeur, calculer une somme, un maximum ou une moyenne nécessite de parcourir tout le tableau : pour $n$ éléments, environ $n$ opérations. On dit que le coût (la complexité) est linéaire, en $O(n)$.

2. Tri par sélection

Méthode · Principe

Pour chaque position $i$, on cherche le plus petit élément de la partie non triée (indices $i$ à $n - 1$) et on l'échange avec l'élément d'indice $i$.

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            if t[j] < t[imin]:
                imin = j
        t[i], t[imin] = t[imin], t[i]

3. Tri par insertion

Tri par insertion : à chaque étape, l'élément suivant est inséré à sa place dans la partie déjà triée (en vert).

Méthode · Principe

def tri_insertion(t):
    for i in range(1, len(t)):
        x = t[i]
        j = i
        while j > 0 and t[j - 1] > x:
            t[j] = t[j - 1]
            j = j - 1
        t[j] = x

4. Correction et coût

Définition · Invariant et terminaison

Un invariant de boucle est une propriété vraie avant et après chaque tour : pour les deux tris, « après le tour $i$, les éléments d'indices $0$ à $i$ sont triés ». Il prouve la correction. La terminaison est assurée par un variant : une quantité entière positive qui décroît strictement (par exemple $j$ dans la boucle while).

Propriété · Coût quadratique

Dans le pire cas, ces tris effectuent environ $\dfrac{n^2}{2}$ comparaisons : coût quadratique, en $O(n^2)$. Doubler la taille du tableau multiplie la durée par environ $4$. Le tri par insertion est rapide sur un tableau presque trié. La fonction sorted de Python est bien plus efficace (en $O(n \log n)$).

Activité · Mesurer les durées

MatérielPython, module time.

ConsigneMesurer la durée du tri par insertion pour des tableaux aléatoires de $1\,000$, $2\,000$ et $4\,000$ éléments.

RésultatPar exemple $0{,}04$ s, $0{,}16$ s, $0{,}65$ s : la durée est environ multipliée par $4$ quand $n$ double.

BilanOn retrouve expérimentalement le coût quadratique.

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

Créer un compte gratuit Se connecter

Coût d'une recherche

★☆☆

Combien de comparaisons au maximum pour chercher une valeur dans un tableau non trié de $1\,000$ éléments ?