Tri
Le tri est le processus de réorganisation d'un ensemble de données dans un ordre spécifique, et c'est l'un des problèmes algorithmiques les plus fondamentaux et les plus profondément étudiés dans le traitement des données.
Famille d'algorithmes de tri
Tri de base (O(n²))
Le tri à bulles, le tri par sélection et le tri par insertion sont simples à implémenter et adaptés aux données à petite échelle ou à l'apprentissage.
Tri avancé (O(n log n))
Le tri rapide, le tri fusion et le tri par tas sont les plus largement utilisés en ingénierie. Le tri de Shell est une amélioration du tri par insertion.
Exemples
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Tri à bulles — O(n²), stable
Chaque passe "fait remonter" le plus grand élément à la fin */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* Optimisation : terminaison anticipée */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* Déjà trié, arrêter tôt */
}
}
/* Fonction de partition Quicksort — O(n log n) en moyenne, instable
Choisir le pivot ; les éléments inférieurs au pivot vont à gauche, les supérieurs vont à droite */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Choisir le dernier élément comme pivot */
int i = low - 1; /* i pointe vers la fin de la région inférieure au pivot */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* Placer le pivot à sa position correcte */
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); /* Indice de partition */
quickSort(arr, low, pi - 1); /* Trier récursivement la moitié gauche */
quickSort(arr, pi + 1, high); /* Trier récursivement la moitié droite */
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("Tri à bulles : "); printArray(arr1, n1);
/* Sortie : 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("Tri rapide : "); printArray(arr2, 7);
/* Sortie : 11 12 22 25 34 64 90 */
return 0;
}
Illustration du concept de diviser pour régner
Tri rapide (partition)
Choisir le pivot
Inférieur au pivot → côté gauche, supérieur → côté droit
Trier récursivement les sous-tableaux gauche et droit
Instable | En place | Le plus couramment utilisé
Tri fusion (Merge)
Diviser récursivement par deux jusqu'à la plus petite unité
Fusionner deux sous-séquences ordonnées
Nécessite un tableau supplémentaire O(n)
Stable | Nécessite de l'espace supplémentaire | Tri externe
Tri par tas (Heapify)
Construire un tas max O(n)
Placer la racine du tas (max) à la fin
Réajuster le tas O(log n)
Instable | En place O(1) | Optimal en espace
Comparaison complète des algorithmes de tri
| Algorithme | Meilleur | Moyenne | Pire | Espace | Stabilité |
|---|---|---|---|---|---|
| Tri à bulles | O(n) | O(n²) | O(n²) | O(1) | Stable |
| Tri par sélection | O(n²) | O(n²) | O(n²) | O(1) | Instable |
| Tri par insertion | O(n) | O(n²) | O(n²) | O(1) | Stable |
| Tri rapide | O(n log n) | O(n log n) | O(n²) | O(log n) | Instable |
| Tri fusion | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable |
| Tri par tas | O(n log n) | O(n log n) | O(n log n) | O(1) | Instable |
| Tri de Shell | O(n log n) | O(n^1.3) | O(n²) | O(1) | Instable |
Autres extensionsConseils pratiques de sélection : pour les scénarios généraux, le tri rapide est le premier choix ; choisissez le tri par fusion lorsqu'une stabilité est nécessaire ; choisissez le tri par tas lorsque la mémoire est extrêmement limitée ; choisissez le tri par insertion pour des données à petite échelle ou presque triées.