17 - Algorithmes de tri

Réponse : B. Un tri en place modifie directement la liste passée en paramètre sans allouer de structure auxiliaire de même taille.

• A est faux : c’est la définition d’un tri non en place (qui crée une copie).
• C est faux : cela n’a aucun rapport avec le tri.
• D est faux : le caractère « en place » ne dépend pas du type des éléments.

Réponse : C. Si deux éléments ont la même clé de tri, un tri stable conserve leur ordre d’apparition initial.

• A est faux : la stabilité ne concerne pas la fiabilité du programme.
• B est faux : cela décrit la complexité constante, pas la stabilité.
• D est faux : un tri stable fonctionne sur n’importe quelle liste.

Réponse : C. Dans le pire cas, les deux algorithmes effectuent de l’ordre de $n(n-1)/2$ comparaisons, soit une complexité quadratique $O(n^2)$.

• A est faux : $O(n)$ est la complexité d’un simple parcours, pas d’un tri par comparaison naïf.
• B est faux : le tri par sélection parcourt toujours toute la sous-liste, ce n’est jamais $O(n)$.
• D est faux : $O(n \log n)$ est atteint par des algorithmes plus avancés (tri fusion, tri rapide en moyenne), pas par le tri par insertion.

Réponse : B. Sur une liste déjà triée, le tri par insertion effectue seulement $n - 1$ comparaisons ($O(n)$), car aucun décalage n’est nécessaire. Le tri par sélection, lui, effectue toujours $n(n-1)/2$ comparaisons, quelle que soit la liste.

• A est faux : c’est le pire cas du tri par insertion (chaque élément doit remonter jusqu’au début).
• C est faux : les doublons ne changent pas fondamentalement les performances relatives.
• D est faux : le tri par insertion a un meilleur cas en $O(n)$, contrairement au tri par sélection.

À l’étape $i = 1$, le minimum est déjà en place : l’échange est un échange « à vide » (l’élément avec lui-même). À l’étape $i = 2$, l’échange de 9 et 5 place directement trois éléments dans l’ordre.

def tri_selection(L):
    for i in range(len(L) - 1):
        i_min = i
        for j in range(i + 1, len(L)):
            if L[j] < L[i_min]:
                i_min = j
        L[i], L[i_min] = L[i_min], L[i]
    return L

assert tri_selection([7, 3, 9, 1, 5]) == [1, 3, 5, 7, 9]
assert tri_selection([1, 2, 3]) == [1, 2, 3]
assert tri_selection([3, 1]) == [1, 3]
assert tri_selection([]) == []
print("Tests OK")

• i_min = i : on suppose que le minimum est à la position courante.
• range(i + 1, len(L)) : on cherche dans la partie non encore triée.
• L[j] < L[i_min] : on compare chaque élément au minimum provisoire.
• L’échange final place le minimum trouvé à la position $i$.

1. Liste [1, 2, 3, 4, 5] :

Total : quatre comparaisons, zéro décalage. C’est le meilleur cas : $O(n)$.

2. Liste [5, 4, 3, 2, 1] :

Total : $1 + 2 + 3 + 4 = 10$ comparaisons et 10 décalages. C’est le pire cas : $O(n^2)$.

3. Le tri par insertion est le plus rapide sur une liste déjà triée (complexité linéaire) et le plus lent sur une liste triée en ordre décroissant (complexité quadratique). C’est pourquoi il est particulièrement adapté aux données « presque triées ».

1. À l’étape $i$ (pour $i$ allant de 0 à $n - 2$), on parcourt les éléments de $i + 1$ à $n - 1$, soit $n - 1 - i$ comparaisons. Le total est : $$C(n) = \sum_{i=0}^{n-2} (n - 1 - i) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$$

2.

• $C(10) = \frac{10 \times 9}{2} = 45$
• $C(100) = \frac{100 \times 99}{2} = 4,950$
• $C(1000) = \frac{1000 \times 999}{2} = 499,500$

3. La complexité est quadratique. Si la taille est multipliée par 10, le temps est multiplié par $10^2 = 100$. Donc pour 10 000 éléments, le temps estimé est $0{,}5 \times 100 = 50$ secondes.

On peut vérifier : $\frac{C(10,000)}{C(1000)} = \frac{10,000 \times 9999}{1000 \times 999} \approx 100{,}1$, ce qui confirme le facteur 100.

4. Le tri par sélection effectue $C(1000) = 499,500$ comparaisons. Le tri par insertion dans le meilleur cas en effectue $999$. Le rapport est $\frac{499,500}{999} \approx 500$. Le tri par insertion est donc environ 500 fois plus rapide sur une liste déjà triée.

def tri_classement(temps, noms):
    """Trie temps par ordre croissant et réorganise noms en parallèle."""
    for i in range(len(temps) - 1):
        i_min = i
        for j in range(i + 1, len(temps)):
            if temps[j] < temps[i_min]:
                i_min = j
        temps[i], temps[i_min] = temps[i_min], temps[i]
        noms[i], noms[i_min] = noms[i_min], noms[i]

temps = [28.4, 25.1, 27.8, 24.9, 26.3, 25.7]
noms = ["Alice", "Bob", "Clara", "David", "Eva", "Franck"]
tri_classement(temps, noms)

for i in range(len(noms)):
    print(f"{i + 1}. {noms[i]} : {temps[i]} s")

Résultat :

1. David : 24.9 s
2. Bob : 25.1 s
3. Franck : 25.7 s
4. Eva : 26.3 s
5. Clara : 27.8 s
6. Alice : 28.4 s

Point clé : quand on échange temps[i] et temps[i_min], il faut aussi échanger noms[i] et noms[i_min] pour que la correspondance nom/temps soit conservée.

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

prenoms = ["Zoé", "Alice", "Marc", "Léa", "Hugo"]
print(tri_insertion(prenoms))
# ['Alice', 'Hugo', 'Léa', 'Marc', 'Zoé']

Le tri par insertion fonctionne identiquement sur des chaînes de caractères, car Python compare les chaînes caractère par caractère selon l’ordre Unicode (qui respecte l’ordre alphabétique pour les lettres sans accent).

Attention : les lettres accentuées (é, è, etc.) ont un code Unicode supérieur aux lettres non accentuées. Pour un tri alphabétique parfait en français, il faudrait utiliser une clé de tri spécifique (hors programme).

1. Initialisation ($i = 0$) : la boucle interne cherche le minimum de toute la liste. Après l’échange, L[0] contient le plus petit élément de la liste. L’invariant est vérifié : L[0] est bien le seul élément des « $0 + 1 = 1$ plus petits », et il est trié (un seul élément).

2. Conservation : supposons l’invariant vrai après l’itération $i$ : L[0], ..., L[i] sont les $i + 1$ plus petits éléments de la liste, triés. À l’itération $i + 1$, la boucle interne cherche le minimum de L[i+1], ..., L[n-1]. Ce minimum est le plus petit des éléments restants, c’est-à-dire le $(i + 2)$-ème plus petit élément de la liste (puisque les $i + 1$ plus petits sont déjà placés). Après l’échange, L[i+1] contient ce minimum. On a donc $L[0] \leq \cdots \leq L[i] \leq L[i+1]$, et les $i + 2$ premiers éléments sont les $i + 2$ plus petits, triés. L’invariant est conservé.

3. Conclusion : après la dernière itération ($i = n - 2$), l’invariant garantit que L[0], ..., L[n-2] sont les $n - 1$ plus petits éléments, triés. Le dernier élément L[n-1] est donc nécessairement le plus grand. La liste entière est triée.

1. Le tri par sélection utilise deux boucles for imbriquées, dont les bornes sont fixées par len(L). Les boucles for en Python terminent toujours car elles parcourent un itérable fini. Il n’y a pas de boucle while, donc la terminaison est garantie.

2. Le tri par insertion utilise une boucle for (terminaison garantie) et une boucle while interne. Pour la boucle while, le variant est $j$ : il est initialisé à $i > 0$, il décroît de 1 à chaque itération (j -= 1), et la boucle s’arrête quand $j = 0$ (ou plus tôt si la condition L[j-1] > en_cours est fausse). Comme $j$ est un entier positif strictement décroissant, la boucle while termine.

import random

def compter_comparaisons_selection(L):
    """Tri par sélection avec compteur de comparaisons."""
    nb_comp = 0
    for i in range(len(L) - 1):
        i_min = i
        for j in range(i + 1, len(L)):
            nb_comp += 1
            if L[j] < L[i_min]:
                i_min = j
        L[i], L[i_min] = L[i_min], L[i]
    return nb_comp

def compter_comparaisons_insertion(L):
    """Tri par insertion avec compteur de comparaisons."""
    nb_comp = 0
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        while j > 0:
            nb_comp += 1
            if L[j - 1] > en_cours:
                L[j] = L[j - 1]
                j -= 1
            else:
                break
        L[j] = en_cours
    return nb_comp

n = 10

# Cas 1 : liste aléatoire
L = [random.randint(0, 100) for _ in range(n)]
c_sel = compter_comparaisons_selection(L.copy())
c_ins = compter_comparaisons_insertion(L.copy())
print(f"Aléatoire  : sélection = {c_sel}, insertion = {c_ins}")

# Cas 2 : liste triée
L = list(range(n))
c_sel = compter_comparaisons_selection(L.copy())
c_ins = compter_comparaisons_insertion(L.copy())
print(f"Triée      : sélection = {c_sel}, insertion = {c_ins}")

# Cas 3 : liste inversée
L = list(range(n, 0, -1))
c_sel = compter_comparaisons_selection(L.copy())
c_ins = compter_comparaisons_insertion(L.copy())
print(f"Inversée   : sélection = {c_sel}, insertion = {c_ins}")

Résultat attendu :

Aléatoire  : sélection = 45, insertion = ~30
Triée      : sélection = 45, insertion = 9
Inversée   : sélection = 45, insertion = 45

Analyse :

• Le tri par sélection effectue toujours $\frac{n(n-1)}{2} = 45$ comparaisons, quel que soit l’ordre initial.
• Le tri par insertion effectue seulement $n - 1 = 9$ comparaisons sur une liste triée (meilleur cas, $O(n)$), mais $\frac{n(n-1)}{2} = 45$ comparaisons sur une liste inversée (pire cas, $O(n^2)$).
• Sur une liste aléatoire, le tri par insertion effectue en moyenne environ $\frac{n(n-1)}{4} \approx 23$ comparaisons.

Ces résultats confirment l’analyse théorique : le tri par insertion est adaptatif (il tire profit de l’ordre existant), contrairement au tri par sélection.