Tri fusion
Tri stable
Tri fusion est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Tri stable
Le tri par fusion est un tri fondé sur le principe « diviser pour régner » : il divise le tableau en deux, trie chaque moitié, puis les fusionne. Sa complexité est O(n log n) dans tous les cas et il est stable.
L’étape de division
Divisez récursivement le tableau au niveau du point central jusqu’à ce que chaque partie ne contienne qu’un élément. Un élément seul est trivialement trié : c’est le cas de base.
L’étape de fusion
L’opération centrale consiste à fusionner deux séquences déjà triées en une seule. Parcourez-les toutes les deux à l’aide de pointeurs d’index, en copiant toujours en premier le plus petit élément en tête.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Pourquoi il est stable
La fusion utilise a[i] <= a[j] : lorsque deux éléments sont égaux, elle prend d’abord celui de la séquence de gauche. Comme cette séquence contenait les éléments antérieurs, l’ordre d’origine est préservé.
Le mécanisme récursif
Le tri par fusion s’appelle récursivement sur chaque moitié, puis les fusionne. Nous transmettons un tampon de travail partagé afin d’éviter d’en allouer un à chaque appel.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Utilisation de la mémoire
Contrairement au tri rapide, le tri par fusion nécessite une mémoire supplémentaire O(n) pour le tampon de fusion. C’est son principal inconvénient pour les très grands tableaux lorsque la mémoire est limitée.
O(n log n) garanti
La récursion divise toujours le tableau en deux, ce qui donne log n niveaux, et chaque niveau fusionne n éléments. Le tri par fusion est donc en O(n log n) dans les cas le meilleur, moyen et le pire, contrairement au tri rapide.
Compter les niveaux de fusion
Le nombre de niveaux de récursion est ceil(log2 n). Calculons-le pour plusieurs tailles.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Tri par fusion ascendant
Une variante itérative fusionne des séquences de taille 1, puis 2, puis 4, en doublant la taille à chaque passe. Elle évite complètement la récursion et convient bien aux listes chaînées.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Quand choisir le tri par fusion
Privilégiez le tri par fusion lorsque vous avez besoin :
- d’une complexité O(n log n) garantie, sans mauvais cas
- de stabilité
- de trier des listes chaînées (aucun accès aléatoire nécessaire)
- d’effectuer un tri externe sur des données trop volumineuses pour la RAM
Tri par fusion ou tri rapide
Le tri rapide est généralement plus rapide en pratique et s’effectue en place, mais il n’est pas stable et peut avoir un très mauvais cas. Le tri par fusion est stable et sa complexité est garantie, mais il utilise davantage de mémoire. Choisissez selon vos contraintes.
Vérification rapide
Testez votre compréhension du tri par fusion.
Récapitulatif
Vous avez appris le tri par fusion.
- Diviser en deux, trier chaque partie, puis fusionner
- Lors de la fusion, privilégier l’élément de gauche en cas de clés égales garantit la stabilité
- Complexité O(n log n) garantie dans tous les cas
- Nécessite O(n) de mémoire supplémentaire ; très adapté aux listes chaînées et aux tris externes
Questions Fréquemment Posées
La leçon « Tri fusion » est-elle gratuite ?
Oui — le texte complet de « Tri fusion » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tri fusion » ?
Tri stable Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Tri fusion » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.