Tri rapide
Diviser pour régner
Tri rapide est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 2 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.
Diviser pour régner
Le tri rapide est un tri fondé sur la méthode « diviser pour régner ». Il choisit un pivot, partitionne le tableau afin que les éléments plus petits aillent à gauche et les plus grands à droite, puis trie récursivement chaque partie.
Sa complexité temporelle moyenne est O(n log n).
L’étape de partitionnement
L’idée essentielle est le partitionnement : réorganiser le tableau autour d’un pivot de sorte que tout ce qui se trouve à gauche du pivot soit plus petit et tout ce qui se trouve à droite soit plus grand. Le pivot se retrouve alors à sa position finale dans le tableau trié.
Schéma de partitionnement de Lomuto
Le schéma de Lomuto utilise le dernier élément comme pivot. Il conserve un indice i marquant la limite des éléments plus petits et effectue des échanges au fur et à mesure du parcours.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Le tri récursif
Le tri rapide appelle le partitionnement, puis effectue un appel récursif sur les deux sous-tableaux situés de part et d’autre du pivot. Le cas de base est un sous-tableau de taille 0 ou 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Choisir un bon pivot
Un mauvais pivot (par exemple toujours le dernier élément lorsque l’entrée est triée) entraîne un comportement en O(n au carré). De meilleurs choix répartissent les partitions plus uniformément.
- Médiane de trois
- Pivot aléatoire
Médiane de trois
La méthode de la médiane de trois choisit comme pivot la médiane du premier, de l’élément du milieu et du dernier élément, ce qui évite le pire cas sur des données déjà triées.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Analyse du pire cas
Si chaque partition ne sépare qu’un seul élément, la profondeur de la récursion atteint n et le coût est O(n au carré). Cela se produit avec un pivot fixe sur une entrée triée ou triée dans l’ordre inverse.
La randomisation rend le pire cas extrêmement improbable.
Pivot aléatoire
Échanger un élément aléatoire avec la position du pivot avant le partitionnement protège contre les entrées conçues pour provoquer le pire cas.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}Sur place et non stable
Le tri rapide trie sur place en utilisant seulement un espace de pile O(log n) en moyenne. Cependant, il n’est pas stable : les éléments égaux peuvent être réordonnés par les échanges effectués lors du partitionnement.
Optimisation des appels terminaux
Effectuer d’abord l’appel récursif sur la moitié la plus petite et utiliser une boucle pour la moitié la plus grande limite la profondeur de la pile à O(log n), ce qui évite son débordement avec les grands tableaux.
Trier des chaînes
La même structure permet de trier tout type comparable. Ici, le tri rapide ordonne un tableau d’entiers, mais il suffit de modifier la comparaison pour gérer d’autres types.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Vérification rapide
Testez votre compréhension du tri rapide.
Récapitulatif
Vous avez appris le tri rapide.
- Partitionnez autour d’un pivot, puis effectuez un appel récursif sur chaque partie
- O(n log n) en moyenne, O(n au carré) dans le pire des cas
- Les pivots choisis par médiane de trois ou aléatoirement évitent le pire cas
- Effectué sur place, mais non stable
Questions Fréquemment Posées
La leçon « Tri rapide » est-elle gratuite ?
Oui — le texte complet de « Tri rapide » 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 rapide » ?
Diviser pour régner 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 2 sur 4.
Combien de temps prend la leçon « Tri rapide » ?
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.