Tri par fusion et tri rapide : cours et exercices corrigés de prépa

Q: Comment fonctionne le tri par fusion ?

On coupe la liste en deux moitiés, on trie chaque moitié par un appel récursif, puis on fusionne les deux moitiés triées : on compare les deux premiers éléments restants, on ajoute le plus petit au résultat et on avance dans sa liste. Le cas de base est une liste d'au plus un élément, déjà triée. On écrit la fusion avec deux indices et `append`, jamais avec `pop(0)` ni des tranches récursives, qui la rendraient quadratique.

Q: Quelle est la complexité du tri par fusion ?

Elle vérifie C(n) = 2C(n/2) + an : deux appels sur des moitiés, puis une fusion en temps linéaire. On obtient O(n log n) au meilleur comme au pire cas ; pour n = 2^k, le nombre de comparaisons est compris entre (n)/(2)log_2 n et n log_2 n - n + 1. En mémoire, il demande O(n) pour les listes créées : ce n'est pas un tri en place.

Q: Comment fonctionne le tri rapide ?

On choisit un élément, le pivot, puis on partitionne la liste : les éléments plus petits que le pivot passent à sa gauche, les autres à sa droite, et le pivot se trouve à sa place définitive. On trie ensuite récursivement les deux côtés, sans le pivot. La version en place du cours travaille sur un segment `L[g..d]` et s'arrête quand `g < d` est faux.

Q: Pourquoi le tri rapide est-il en O(n^2) dans le pire cas ?

Si le pivot est chaque fois le plus petit ou le plus grand élément de son segment, la partition laisse un côté vide et l'autre de n - 1 éléments : on obtient C(n) = C(n - 1) + an, soit (n(n-1))/(2) comparaisons. C'est le cas d'une liste déjà triée avec le pivot premier, et aussi d'une liste de valeurs toutes égales avec la partition du cours. Au meilleur cas, le pivot partage chaque segment en deux moitiés : O(n log n).

Q: Comment choisir le pivot du tri rapide ?

Le pivot premier ou dernier est quadratique sur une liste triée. Le pivot du milieu est très bon sur une liste triée, mais une entrée construite exprès le rend quadratique. Un pivot tiré au hasard rend le pire cas très improbable pour toute entrée. Quand beaucoup de valeurs se répètent, on partitionne en trois zones (plus petits, égaux, plus grands) pour éviter le cas quadratique.

Q: Le tri par fusion et le tri rapide sont-ils stables et en place ?

Un tri est stable si deux éléments de même clé gardent leur ordre de départ, et en place s'il n'utilise qu'une mémoire indépendante de n en plus de la liste. Le tri par fusion, avec une fusion qui compare par `<=`, est stable mais pas en place. Le tri rapide du cours est en place, mais pas stable ; sa pile d'appels a une profondeur de log_2 n au mieux et n au pire.

MP
PSI
TSI 2
Offert à l'essai

Diviser pour régner, fusion de deux listes triées, tri par fusion, partition et tri rapide, choix du pivot, complexités temporelle et spatiale au meilleur et au pire cas, stabilité, tri en place, tri selon une clé.

15méthodes
32exercices corrigés
3problèmes
18pièges
34figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Le tri par fusion et le tri rapide sont les deux tris efficaces du programme de deuxième année en MP, PSI et TSI au Maroc. Tous deux reposent sur l'idée diviser pour régner : le tri par fusion coupe la liste en deux, trie chaque moitié, puis fusionne les deux moitiés triées ; le tri rapide range les éléments autour d'un pivot par une partition, puis trie chaque côté. Le tri par fusion est en $O(n \log n)$ dans tous les cas et stable, mais il n'est pas en place ; le tri rapide est en place, en $O(n \log n)$ au meilleur cas et en $O(n^2)$ au pire cas, selon le choix du pivot. Les sujets du CNC demandent souvent d'écrire un tri selon une clé, sans sort ni sorted, parfois avec une complexité imposée. Tu y trouves la fusion par indices, les deux tris en Python avec leurs preuves, leur complexité en temps et en mémoire, la stabilité et le tri en place, puis des exercices corrigés tirés des sujets du CNC.

Ce que tu sauras faire

Trier une liste est l'opération la plus fréquente d'un programme qui traite des données : on trie pour chercher vite, pour repérer des doublons, pour classer des résultats. Les tris de première année coûtent de l'ordre de $n^2$ comparaisons dans le pire cas ; ce chapitre étudie deux tris en $O(n \log n)$ , bâtis sur l'idée « diviser pour régner ». À la fin de ce chapitre, tu dois savoir :

écrire la fusion de deux listes triées et le tri par fusion, les dérouler à la main, prouver qu'ils terminent et qu'ils sont justes ;
écrire une partition autour d'un pivot et le tri rapide, en place ou avec des listes auxiliaires ;
calculer leur complexité en temps et en mémoire, au meilleur et au pire cas, et écrire une entrée de chaque cas ;
discuter le choix du pivot ;
dire si un tri est stable, s'il est en place, et adapter un tri à une clé (une composante d'un tuple, une longueur, une distance) ;
comparer les tris du programme et choisir celui qui convient, puis vérifier ce choix par la mesure.

L'essentiel : Diviser pour régner Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Définitions

Diviser pour régner : diviser le problème en sous-problèmes plus petits, les résoudre par des appels récursifs, combiner leurs solutions.
Tri en place : la liste reçue est réorganisée avec une mémoire supplémentaire indépendante de $n$ , pile d'appels mise à part.
Tri stable : deux éléments de même clé gardent leur ordre de départ.

Le tri par fusion travaille en combinant (la fusion) ; le tri rapide travaille en divisant (la partition).

Une méthode du chapitre Extrait gratuit

Méthode Écrire la fusion de deux listes triées

Quand l’utiliser

Toute question qui demande de réunir deux listes déjà triées en une liste triée, d'écrire un tri par fusion, ou une fonction qui parcourt deux listes triées en parallèle (union, intersection, comptage).

Rappel de cours

Deux indices i et j avancent dans A et B ; à chaque tour, on compare A[i] et B[j], on ajoute le plus petit à R par append et l'on avance l'indice correspondant ; quand une liste est épuisée, on ajoute le reste de l'autre. Test <= pour prendre l'élément de A en cas d'égalité. Coût $O(n_1 + n_2)$ (cours, section 3).

Démarche

Initialiser R = [], i = 0, j = 0.
Écrire la boucle while i < len(A) and j < len(B) avec le test A[i] <= B[j].
Écrire les deux boucles qui ajoutent les restes.
Renvoyer R (ne pas oublier le return).
Tester à la main : une liste vide, des égalités, une liste entièrement plus petite que l'autre.

Rédaction type

Le code de la fonction fusion du cours (section 3.2), puis : « La première boucle fait au plus $n_1 + n_2 - 1$ tours, les deux autres $n_1 + n_2$ ajouts au plus en tout ; chaque tour est en temps constant (append en $O(1)$ ) : la complexité est en $O(n_1 + n_2)$ . »

Exemple traité

fusion([1, 4, 4, 9], [2, 4, 7]) : on prend 1, puis 2 ; on compare 4 et 4 : le test <= prend le 4 de A, puis le second 4 de A (comparé à 4) ; on compare 9 et 4, on prend le 4 de B, puis 7 ; B est épuisée, on ajoute 9. Résultat [1, 2, 4, 4, 4, 7, 9], en 6 comparaisons (compté par programme). Les deux 4 de A passent avant celui de B.

Erreurs fréquentes

Écrire R = R + [x] ou A.pop(0) : chaque ajout ou retrait coûte $O(n)$ , la fusion devient quadratique.
Écrire la fusion récursivement avec des tranches : $O(n^2)$ éléments recopiés et RecursionError au-delà d'environ 1000 éléments en tout (cours, section 3.5).
Oublier les restes, ou le return.
Écrire < au lieu de <= : le résultat est le même pour des nombres, mais le tri par fusion n'est plus stable.

Pour s’entraîner

Exercices 1, 2, 18, 19, 27, 28 et 31, problème 1.

Un exercice corrigé Extrait gratuit

Exercice Trier une séquence ★☆☆

Une séquence est un ensemble d'éléments non vide, fini et ordonné ; on la représente par une liste. Dans cette partie, les éléments des séquences sont des entiers positifs.

Q.1. Écrire la fonction tri_sequence(S) qui reçoit en paramètre une séquence S et qui trie les éléments de S dans l'ordre croissant. Exemple : pour S = [6, 23, 20, 18, 6, 54, 3, 13, 6, 18], après l'appel tri_sequence(S), on obtient la séquence [3, 6, 6, 6, 13, 18, 18, 20, 23, 54].

Question A. (Question ajoutée.) Déterminer la complexité de la fonction écrite, au meilleur et au pire cas, et la comparer à celle d'un tri par sélection.

L'énoncé ne dit pas si tri_sequence doit modifier S ou renvoyer une copie triée ; on traitera les deux.

Indications

Méthode 2 : le tri par fusion du cours renvoie une nouvelle liste triée.
Méthode 13 : pour que l'appel modifie S elle-même, on recopie la liste triée dans S, case par case.
Méthode 8 : la récurrence du tri par fusion ne dépend pas de l'ordre des éléments.

Correction détaillée

Q.1. Analyse. L'exemple du sujet dit « après l'appel, on obtient la séquence » : il suggère que S elle-même est triée. On écrit d'abord la version qui renvoie une copie triée, puis celle qui trie S en recopiant le résultat dans ses cases. Le sujet n'interdit pas sort, mais une réponse S.sort() ne montre aucun algorithme ; elle rapporte peu de points quand la question demande d'écrire un tri.

def tri_sequence_copie(S):
    # S : liste d'entiers ; renvoie une nouvelle liste
    # triée dans l'ordre croissant ; S n'est pas modifiée
    return tri_fusion(S)

def tri_sequence(S):
    # S : liste d'entiers ; trie S elle-même dans
    # l'ordre croissant ; ne renvoie rien
    T = tri_fusion(S)
    for i in range(len(S)):
        S[i] = T[i]

S = [6, 23, 20, 18, 6, 54, 3, 13, 6, 18]
print(tri_sequence_copie(S))
tri_sequence(S)
print(S)

Le programme affiche :

[3, 6, 6, 6, 13, 18, 18, 20, 23, 54]
[3, 6, 6, 6, 13, 18, 18, 20, 23, 54]

Question A. Notons $n$ la longueur de S. tri_fusion vérifie $C(n) = 2C(n/2) + an$ au meilleur comme au pire cas : deux appels sur des moitiés, puis une fusion et deux tranches en $O(n)$ . Pour $n = 2^k$ , cette récurrence donne $C(n) = O(n \log n)$ (méthode 10 du chapitre 1). La recopie dans S ajoute $n$ affectations, en $O(n)$ . La complexité de tri_sequence est donc en $O(n \log n)$ , au meilleur comme au pire cas.

Le tri par sélection fait toujours $\frac{n(n-1)}{2}$ comparaisons, quelle que soit la liste : il est en $O(n^2)$ au meilleur comme au pire cas. Pour $n = 1000$ , cela fait 499 500 comparaisons, alors que le tri par fusion en fait au plus 8977 (borne calculée par programme en ajoutant, fusion par fusion, le maximum $n_1 + n_2 - 1$ de l'exercice 1).

Méthodes à retenir

« Trier les éléments de S » peut vouloir dire modifier S ; une recopie finale règle la question sans changer la complexité. Le tri par fusion garantit $O(n \log n)$ dans tous les cas. Voir les méthodes 2, 8 et 13.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 15 méthodes, 18 pièges corrigés, la carte mentale, 32 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

1. Pourquoi trier vite
- 1.1 Les tris de première année
- 1.2 Un ordre de grandeur
- 1.3 Trier au concours
- 1.4 Deux mots à rappeler
2. Diviser pour régner
- 2.1 Le principe
- 2.2 Deux façons de partager le travail
3. Fusion de deux listes triées
- 3.1 L'idée
- 3.2 Le code
- 3.3 Terminaison et correction
- 3.4 Coût de la fusion
- 3.5 Trois façons de mal fusionner
4. Le tri par fusion
- 4.1 L'algorithme
- 4.2 La trace : découpe, puis fusions
- 4.3 Terminaison et correction
- 4.4 Complexité en temps
- 4.5 Complexité en mémoire
5. Partition autour d'un pivot
- 5.1 L'idée
- 5.2 La partition en place
- 5.3 Invariant et coût
6. Le tri rapide
- 6.1 Avec des listes auxiliaires
- 6.2 En place
- 6.3 Terminaison et correction
- 6.4 Le pire cas
- 6.5 Le meilleur cas
- 6.6 Le cas moyen
- 6.7 La mémoire et la pile
7. Le choix du pivot
- 7.1 Ce que chaque choix change
- 7.2 Le pivot au hasard
- 7.3 Ce que le hasard ne change pas
- 7.4 Deux améliorations
8. Stabilité et tri en place
- 8.1 La stabilité des deux tris
- 8.2 Rendre un tri stable
- 8.3 En place, et la liste reçue
9. Trier selon une clé
- 9.1 Trier des tuples selon une composante
- 9.2 Une clé coûteuse : la calculer une fois
- 9.3 L'ordre décroissant
- 9.4 Trier des chaînes
10. Comparer les tris et choisir
- 10.1 Le tableau des tris
- 10.2 Mesurer
- 10.3 Les tris de Python
- 10.4 Applications et choix

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Écrire la fusion de deux listes triées
Écrire un tri par fusion récursif
Dérouler un tri par fusion à la main
Écrire une partition en place et dérouler ses échanges
Écrire un tri rapide en place à partir d'une partition
Écrire un tri rapide à listes auxiliaires sans perdre de doublon
Prouver la terminaison et la correction d'un tri récursif
Calculer la complexité en temps d'un tri récursif, au meilleur et au pire cas
Trouver une entrée de meilleur cas et une entrée de pire cas
Calculer la complexité en mémoire d'un tri
Discuter le choix du pivot
Décider si un tri est stable, et le rendre stable
Décider si un tri est en place, et respecter la liste reçue
Trier selon une clé sans sort ni sorted
Choisir et justifier un tri, puis vérifier par la mesure

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Dérouler une fusion et compter ses comparaisons
Réunir deux listes triées sans doublon
Dérouler un tri par fusion
Dérouler une partition et un tri rapide
Trier une séquence
Le tri rapide qui perd des doublons
Un cas de base qui manque
Entrées de meilleur et de pire cas
Stable ou non
En place ou non, et la liste reçue
La médiane par un tri
Vérifier qu'une liste est triée
Combien de comparaisons pour $n = 2^k$

Entraînement (14)

Trier des images par distance
Les mots les plus proches
Trier les cases d'une grille
Compléter un tri rapide à partir d'une partition donnée
La fusion récursive par tranches
Ajouts par concaténation et pop(0)
Un tri par fusion en quatre morceaux
Le tri par fusion ascendant, sans récursion
Des valeurs toutes égales
Quatre façons de choisir le pivot
La profondeur de pile du tri rapide
Rendre un tri stable
Trier par deux clés
Fusionner $k$ listes triées

Approfondissement (5)

Compter les inversions par une fusion
Le $k$ -ième plus petit élément par partition
Pivot d'un tri rapide et insertion pour les petits segments
Intersection de deux listes triées
Les plus longues sous-séquences croissantes

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Compression de Huffman : fréquences, tri et insertion
CNC 2017, filières MP, PSI et TSI, épreuve d'informatique, partie II « Programmation Python : la compression de Huffman », questions II.3, II.4 et II.5-a, complétée
La transformée de Burrows-Wheeler
CNC 2020, filière PSI, épreuve d'informatique, partie III « Transformée de Burrows-Wheeler », questions 1 à 5, complétée
Trier les villes d'un réseau routier
CNC 2019, filière PSI, épreuve d'informatique, problème « Réseau routier », partie I « Modélisation d'un réseau routier », questions 1 à 5, complétée

Questions fréquentes

Comment fonctionne le tri par fusion ?

On coupe la liste en deux moitiés, on trie chaque moitié par un appel récursif, puis on fusionne les deux moitiés triées : on compare les deux premiers éléments restants, on ajoute le plus petit au résultat et on avance dans sa liste. Le cas de base est une liste d'au plus un élément, déjà triée. On écrit la fusion avec deux indices et append, jamais avec pop(0) ni des tranches récursives, qui la rendraient quadratique.

Quelle est la complexité du tri par fusion ?

Elle vérifie $C(n) = 2C(n/2) + an$ : deux appels sur des moitiés, puis une fusion en temps linéaire. On obtient $O(n \log n)$ au meilleur comme au pire cas ; pour $n = 2^k$ , le nombre de comparaisons est compris entre $\frac{n}{2}\log_2 n$ et $n \log_2 n - n + 1$ . En mémoire, il demande $O(n)$ pour les listes créées : ce n'est pas un tri en place.

Comment fonctionne le tri rapide ?

On choisit un élément, le pivot, puis on partitionne la liste : les éléments plus petits que le pivot passent à sa gauche, les autres à sa droite, et le pivot se trouve à sa place définitive. On trie ensuite récursivement les deux côtés, sans le pivot. La version en place du cours travaille sur un segment L[g..d] et s'arrête quand g < d est faux.

Pourquoi le tri rapide est-il en

O(n^2)

dans le pire cas ?

Si le pivot est chaque fois le plus petit ou le plus grand élément de son segment, la partition laisse un côté vide et l'autre de $n - 1$ éléments : on obtient $C(n) = C(n - 1) + an$ , soit $\frac{n(n-1)}{2}$ comparaisons. C'est le cas d'une liste déjà triée avec le pivot premier, et aussi d'une liste de valeurs toutes égales avec la partition du cours. Au meilleur cas, le pivot partage chaque segment en deux moitiés : $O(n \log n)$ .

Comment choisir le pivot du tri rapide ?

Le pivot premier ou dernier est quadratique sur une liste triée. Le pivot du milieu est très bon sur une liste triée, mais une entrée construite exprès le rend quadratique. Un pivot tiré au hasard rend le pire cas très improbable pour toute entrée. Quand beaucoup de valeurs se répètent, on partitionne en trois zones (plus petits, égaux, plus grands) pour éviter le cas quadratique.

Le tri par fusion et le tri rapide sont-ils stables et en place ?

Un tri est stable si deux éléments de même clé gardent leur ordre de départ, et en place s'il n'utilise qu'une mémoire indépendante de $n$ en plus de la liste. Le tri par fusion, avec une fusion qui compare par <=, est stable mais pas en place. Le tri rapide du cours est en place, mais pas stable ; sa pile d'appels a une profondeur de $\log_2 n$ au mieux et $n$ au pire.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Tri par fusion et tri rapide : cours et exercices corrigés de prépa

Ce que tu sauras faire

L'essentiel : Diviser pour régner Extrait gratuit

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Plan du cours

Les méthodes du chapitre

Les exercices corrigés

Application directe (13)

Entraînement (14)

Approfondissement (5)

Les problèmes de concours

Questions fréquentes

Comment y accéder

Toute ta prépa au même endroit