28 - Algorithmes de tri

Les exercices se font dans Thonny, dans le fichier 28_algorithmes_de_tri.py.

Cours associé : 20 - Tris .

Exercice 1 : QCM – vérification des prérequis

Pour chaque question, une seule réponse est correcte.

1. Qu’est-ce qu’un tri « en place » ?

A. Un tri qui ne modifie pas la liste d’origine
B. Un tri qui trie directement dans la structure de données initiale, sans créer de nouvelle liste
C. Un tri qui place chaque élément à une position aléatoire
D. Un tri qui fonctionne uniquement sur des listes d’entiers

Correction publiée après la séance.

2. Qu’est-ce qu’un tri « stable » ?

A. Un tri qui ne plante jamais
B. Un tri dont la complexité ne varie pas selon les données
C. Un tri qui préserve l’ordre relatif des éléments considérés comme égaux
D. Un tri qui fonctionne uniquement sur des listes déjà presque triées

Correction publiée après la séance.

3. Quelle est la complexité au pire cas du tri par sélection et du tri par insertion ?

A. Les deux sont en $O(n)$
B. Le tri par sélection est en $O(n)$, le tri par insertion est en $O(n^2)$
C. Les deux sont en $O(n^2)$
D. Le tri par sélection est en $O(n^2)$, le tri par insertion est en $O(n \log n)$

Correction publiée après la séance.

4. Dans quel cas le tri par insertion est-il plus efficace que le tri par sélection ?

A. Quand la liste est triée en ordre décroissant
B. Quand la liste est déjà triée ou presque triée
C. Quand la liste contient des doublons
D. Les deux ont toujours exactement les mêmes performances

Correction publiée après la séance.

Exercice 2 : tri par insertion pas à pas

On trie la liste [5, 2, 8, 3] avec la fonction du cours :

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]  # décalage vers la droite
            j -= 1
        L[j] = en_cours       # insertion à la bonne place
    return L

Recopier et compléter le tableau, qui suit l’exécution de tri_insertion([5, 2, 8, 3]). La première ligne est donnée.

`i`	Élément à insérer	Partie déjà triée	Décalages effectués	Liste après insertion
1	2	`[5]`	2 < 5 : on décale 5	`[2, 5, 8, 3]`
2
3

Indice

À l’étape i, l’élément à insérer est L[i], et la partie déjà triée est formée des éléments placés à sa gauche. On le compare à ses voisins de gauche, du plus proche au plus lointain : chaque voisin plus grand est décalé d’une case vers la droite, et on s’arrête au premier voisin plus petit ou égal.

Combien de décalages ont été effectués au total ?
Indice
Additionner les décalages de la colonne « Décalages effectués », ligne par ligne.
Pourquoi la boucle while s’arrête-t-elle toujours ? Donner un variant.
Indice
Que devient j à chaque tour de la boucle while, et que se passe-t-il quand j vaut 0 ?
Quelle liste de quatre éléments demande le plus de décalages ? Combien en faut-il alors ?
Indice
Le nombre de décalages est le plus grand quand chaque élément doit aller tout au début de la partie triée, c’est-à-dire quand il est plus petit que tous ceux qui le précèdent. Dans quel ordre les éléments doivent-ils alors être rangés ?

Correction publiée après la séance.

Exercice 3 : traces guidées

3.1 Trace du tri par sélection

Le tri par sélection consiste à chercher le minimum de la partie non triée, puis à l’échanger avec le premier élément non trié.

Compléter la trace pour la liste [7, 3, 9, 1, 5] :

Étape	Partie triée	Partie non triée	Minimum trouvé	Échange	Liste après
$i = 0$	`[]`	`[7, 3, 9, 1, 5]`	… (indice …)	7 ↔ …	`[..., ..., ..., ..., ...]`
$i = 1$	`[1]`	`[3, 9, 7, 5]`	… (indice …)	… ↔ …	`[..., ..., ..., ..., ...]`
$i = 2$	`[1, 3]`	`[9, 7, 5]`	… (indice …)	… ↔ …	`[..., ..., ..., ..., ...]`
$i = 3$	`[1, 3, 5]`	`[7, 9]`	… (indice …)	… ↔ …	`[..., ..., ..., ..., ...]`

Indice

À chaque étape, chercher le plus petit élément de la partie non triée et noter son indice dans la liste complète, puis l’échanger avec l’élément d’indice i. La colonne « Liste après » donne toute la liste après cet échange ; si le minimum est déjà à sa place, l’échange ne change rien.

Correction publiée après la séance.

3.2 Compléter le tri par sélection

Compléter la fonction suivante :

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

Indice

i_min mémorise l’indice du plus petit élément trouvé : au départ, celui de la position i. La boucle sur j examine la partie non triée, qui commence juste après i, en comparant L[j] au minimum provisoire. Enfin, l’échange place ce minimum à la position i.

Correction publiée après la séance.

Exercice 4 : tri par insertion – cas particuliers

1. Tracer l’exécution du tri par insertion sur la liste [1, 2, 3, 4, 5] (déjà triée). Combien de comparaisons sont effectuées ?

Indice

Reprendre le tableau de l’exercice 2. Pour chaque élément inséré, combien de fois la comparaison L[j - 1] > en_cours est-elle faite avant que la boucle while s’arrête ?

2. Tracer l’exécution sur la liste [5, 4, 3, 2, 1] (ordre décroissant). Combien de comparaisons et de décalages sont effectués ?

Indice

Ici, chaque élément est plus petit que tous ceux qui le précèdent : il est comparé à chacun d’eux et les décale tous. L’élément d’indice i demande donc i comparaisons et i décalages.

3. Conclure : dans quel cas le tri par insertion est-il le plus rapide ? Le plus lent ?

Indice

Comparer les totaux des questions 1 et 2 : quel ordre de départ demande le moins de travail, lequel en demande le plus ?

Correction publiée après la séance.

Exercice 5 : compter les opérations (mathématiques)

1. Le tri par sélection effectue toujours le même nombre de comparaisons, quelle que soit la liste. Pour une liste de $n$ éléments, montrer que ce nombre vaut : $$C(n) = \frac{n(n-1)}{2}$$

Indice

À l’étape i, la boucle sur j va de i + 1 à $n - 1$ : combien de comparaisons cela fait-il ? Additionner ces nombres pour i allant de 0 à $n - 2$, en reconnaissant la somme $1 + 2 + \cdots + (n - 1)$.

2. Calculer $C(10)$, $C(100)$ et $C(1000)$.

Indice

Remplacer $n$ par 10, 100 puis 1000 dans la formule, ou bien écrire une fonction C(n) qui renvoie n * (n - 1) // 2 et l’appeler pour chaque valeur.

3. Si le tri par sélection met 0,5 seconde pour trier 1000 éléments, estimer le temps nécessaire pour 10 000 éléments. Justifier.

Indice

Le nombre de comparaisons est proche de $\frac{n^2}{2}$ : quand $n$ est multiplié par 10, par combien ce nombre est-il multiplié ? Le temps varie dans la même proportion.

4. Le tri par insertion, dans le meilleur cas, effectue $n - 1$ comparaisons. Combien de fois est-il plus rapide que le tri par sélection sur une liste déjà triée de 1000 éléments ?

Indice

Calculer le rapport entre $C(1000)$, le nombre de comparaisons du tri par sélection, et $1000 - 1$, celui du tri par insertion sur une liste déjà triée.

Correction publiée après la séance.

Exercice 6 : tri de données réelles

6.1 Classement sportif (sport)

Les temps (en secondes) de six nageurs sur un 50 m sont :

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

Adapter le tri par sélection pour trier la liste temps tout en réorganisant la liste noms de la même façon (quand on échange deux temps, on échange aussi les noms correspondants).

Indice

Reprendre le tri par sélection de l’exercice 3.2 en remplaçant L par temps. La recherche du minimum ne regarde que temps ; à chaque échange de deux temps, faire le même échange dans noms.

Code à copier puis compléter

def tri_classement(temps, noms):
    for i in range(len(temps) - 1):
        i_min = i
        for j in range(i + 1, len(temps)):
            if temps[j] < ...:
                i_min = j
        temps[i], temps[i_min] = temps[i_min], temps[i]
        noms[i], noms[i_min] = ...

tri_classement(temps, noms)

Afficher le classement final (du plus rapide au plus lent).
Indice
Après le tri, noms[i] et temps[i] sont le nom et le temps du nageur classé à la place i + 1 : une boucle sur les indices et une f-string suffisent.

Correction publiée après la séance.

6.2 Tri alphabétique (vie courante)

On dispose d’une liste de prénoms : ["Zoé", "Alice", "Marc", "Léa", "Hugo"].

Trier cette liste par ordre alphabétique en utilisant le tri par insertion.
Indice
La fonction tri_insertion de l’exercice 2 convient telle quelle, car les chaînes se comparent avec > dans l’ordre alphabétique. La recopier, puis l’appeler sur la liste des prénoms et afficher le résultat.
Rappel : en Python, les chaînes de caractères sont comparables avec <, >, etc. (ordre lexicographique).

Correction publiée après la séance.

Exercice 7 : preuve de correction

7.1 Invariant du tri par sélection

On considère le tri par sélection :

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

Invariant proposé : « à la fin de l’itération $i$, les éléments L[0], ..., L[i] sont les $i + 1$ plus petits éléments de la liste originale, et ils sont triés. »

Initialisation : vérifier que l’invariant est vrai après la première itération ($i = 0$).
Indice
Pendant l’itération $i = 0$, la boucle sur j parcourt toute la liste : que contient L[0] après l’échange ? Une liste d’un seul élément est-elle triée ?
Conservation : montrer que si l’invariant est vrai après l’itération $i$, il est encore vrai après l’itération $i + 1$.
Indice
Supposer l’invariant vrai après l’itération $i$. L’itération $i + 1$ cherche le minimum de L[i+1], …, L[n-1] : pourquoi est-il supérieur ou égal à L[i], et où l’échange le place-t-il ?
Conclusion : en déduire que le tri par sélection est correct.
Indice
Appliquer l’invariant après la dernière itération, $i = n - 2$ : que sait-on de L[0], …, L[n-2] ? Où se trouve alors le plus grand élément ?

Correction publiée après la séance.

7.2 Terminaison

Justifier la terminaison du tri par sélection (la boucle for suffit-elle ?).
Indice
Une boucle for sur un range(...) fait un nombre de tours fixé à l’avance. Le tri par sélection contient-il une boucle while ?
Justifier la terminaison du tri par insertion. Quel est le variant de la boucle while interne ?
Indice
Seule la boucle while pose question. Que devient j à chaque tour, et qu’arrive-t-il quand j atteint 0 ?

Correction publiée après la séance.

Exercice 8 : synthèse – comparaison expérimentale

On souhaite comparer expérimentalement les deux algorithmes de tri.

Écrire une fonction compter_comparaisons_selection(L) qui trie la liste par sélection et renvoie le nombre de comparaisons effectuées.

Indice

Reprendre le tri par sélection avec un compteur qui part de 0 et augmente de 1 juste avant chaque comparaison L[j] < L[i_min], puis le renvoyer à la fin.

Code à copier puis compléter

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

Écrire une fonction compter_comparaisons_insertion(L) qui trie la liste par insertion et renvoie le nombre de comparaisons effectuées.

Indice

La comparaison L[j - 1] > en_cours est dans la condition du while : il faut compter aussi celle qui arrête la boucle. Écrire plutôt while j > 0:, puis faire la comparaison dans la boucle avec un if, en comptant chaque comparaison ; quand elle est fausse, sortir de la boucle avec break.

Code à copier puis compléter

def compter_comparaisons_insertion(L):
    nb_comp = 0
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        while j > 0:
            nb_comp = ...
            if L[j - 1] > en_cours:
                L[j] = L[j - 1]
                j = ...
            else:
                break
        L[j] = en_cours
    return nb_comp

Tester les deux fonctions sur les trois cas suivants (avec $n = 10$) :
- une liste aléatoire ;
- une liste déjà triée ;
- une liste triée en ordre décroissant.
Indice
list(range(10)) donne une liste triée et list(range(10, 0, -1)) une liste en ordre décroissant ; pour une liste aléatoire, ajouter dix appels à random.randint dans une boucle. Chaque fonction modifie la liste reçue : lui passer une copie, L.copy(), pour trier la même liste avec les deux méthodes.
Que constate-t-on ? Les résultats sont-ils conformes à l’analyse théorique ?
Indice
Comparer les nombres obtenus aux résultats des exercices 4 et 5 : $\frac{n(n-1)}{2}$ comparaisons pour le tri par sélection dans tous les cas, $n - 1$ pour le tri par insertion sur une liste déjà triée.

Correction publiée après la séance.

27 - Algorithmique 29 - Réseaux (1)