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

Famille d'algorithmes de tri — Comparaison de la complexité temporelle et des caractéristiques

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

#include <stdio.h>

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

Trois principaux algorithmes de tri en O(n log n) — Comparaison des stratégies 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

AlgorithmeMeilleurMoyennePireEspaceStabilité
Tri à bullesO(n)O(n²)O(n²)O(1)Stable
Tri par sélectionO(n²)O(n²)O(n²)O(1)Instable
Tri par insertionO(n)O(n²)O(n²)O(1)Stable
Tri rapideO(n log n)O(n log n)O(n²)O(log n)Instable
Tri fusionO(n log n)O(n log n)O(n log n)O(n)Stable
Tri par tasO(n log n)O(n log n)O(n log n)O(1)Instable
Tri de ShellO(n log n)O(n^1.3)O(n²)O(1)Instable

Conseils 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.

Autres extensions