Implémentation du tri rapide en C : guide pratique et analyse

Le tri rapide, ou Quicksort, est l’un des algorithmes de tri les plus efficaces et largement utilisés en informatique. Développé par Tony Hoare en 1960, cet algorithme repose sur le paradigme « diviser pour régner ». Sa rapidité et sa simplicité d’implémentation en font un choix idéal pour une large gamme d’applications, notamment dans les systèmes où les performances sont critiques.

Dans cet article, nous allons explorer en détail le fonctionnement de l’algorithme Quicksort, son implémentation en langage C et son analyse en termes de complexité. Vous découvrirez également des cas pratiques et des exercices pour renforcer votre compréhension de cet outil puissant. Que vous soyez débutant ou expérimenté, ce guide vous fournira des bases solides pour appliquer le tri rapide dans vos projets.

Sommaire

Présentation du tri rapide (Quicksort)

Définition et principe

Le tri rapide, ou Quicksort, est un algorithme de tri basé sur le principe du partitionnement. Il fonctionne en sélectionnant un élément pivot, puis en réorganisant les autres éléments du tableau de manière à ce que ceux inférieurs au pivot soient placés avant lui et ceux supérieurs après. Cette opération est répétée récursivement sur les sous-tableaux résultants jusqu’à ce que le tableau entier soit trié.

Caractéristiques principales

Algorithme diviser pour régner : Le tableau est divisé en sous-tableaux plus petits, triés indépendamment.
Utilisation d’un pivot : Le pivot est au cœur de l’algorithme, déterminant la manière dont les éléments sont partagés entre les deux parties du tableau.
Récursivité : L’algorithme est appliqué récursivement sur les sous-parties générées.

Avantages du Quicksort

Rapidité : En moyenne, Quicksort a une complexité de (O(n \log n)), ce qui en fait l’un des algorithmes de tri les plus rapides.
Efficacité en mémoire : Quicksort utilise souvent un espace auxiliaire minimal, surtout dans sa version en place.

Inconvénients du Quicksort

Cas pire : Dans le pire des cas, la complexité atteint (O(n^2)), généralement si le pivot est mal choisi (par exemple, le plus petit ou le plus grand élément).
Dépendant du choix du pivot : Un mauvais choix du pivot peut fortement dégrader les performances.

Le tri rapide est particulièrement utile pour les structures de données où des comparaisons fréquentes doivent être effectuées, comme dans le tri de grandes bases de données ou pour les traitements en temps réel.

Fonctionnement de l’algorithme Quicksort

Étapes clés de l’algorithme

Choix du pivot : Un élément du tableau est sélectionné comme pivot. Le choix peut être arbitraire, mais des stratégies courantes incluent le premier élément, le dernier élément, ou un élément médian.
Partitionnement : Les éléments du tableau sont réorganisés de manière à ce que :

Les éléments inférieurs au pivot soient placés à gauche.
Les éléments supérieurs au pivot soient placés à droite.

Appel récursif : L’algorithme est appliqué récursivement sur les sous-tableaux gauche et droit.
Condition d’arrêt : La récursion s’arrête lorsque le sous-tableau contient un ou zéro élément, car il est alors déjà trié.

Pseudocode de Quicksort

Voici une version simplifiée en pseudocode pour illustrer le fonctionnement :

function quicksort(array, low, high):
    if low < high:
        pivotIndex = partition(array, low, high)
        quicksort(array, low, pivotIndex - 1)
        quicksort(array, pivotIndex + 1, high)

function partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j from low to high - 1:
        if array[j] <= pivot:
            i = i + 1
            swap(array[i], array[j])
    swap(array[i + 1], array[high])
    return i + 1

Partitionnement en détail

Le processus de partitionnement est essentiel pour l’efficacité de Quicksort. Voici une description pas à pas :

Initialiser un pointeur (i) à (low – 1), représentant la position des éléments inférieurs au pivot.
Parcourir les éléments du tableau avec un pointeur (j), en comparant chaque élément au pivot.
Si un élément est inférieur ou égal au pivot, incrémenter (i) et échanger les positions des éléments à (i) et (j).
Placer finalement le pivot à sa position correcte en l’échangeant avec l’élément suivant (i).

Illustration avec un exemple

Considérons le tableau suivant :
[ 10, 80, 30, 90, 40, 50, 70 ]

Pivot choisi : (70).
Partitionnement : Les éléments sont réorganisés en deux groupes :

Inférieurs à (70) : (10, 30, 40, 50).
Supérieurs à (70) : (80, 90).
Après partitionnement, le tableau devient :
[ 10, 30, 40, 50, 70, 80, 90 ].

Résultat final

Une fois le processus récursif complété, le tableau est trié en ordre croissant. Cette méthode garantit une division logique des tâches pour une efficacité optimale.

Implémentation en C avec explication du code

Code complet pour Quicksort

Voici une implémentation simple de l’algorithme Quicksort en langage C :

#include <stdio.h>

// Fonction pour échanger deux éléments
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Fonction de partitionnement
int partition(int array[], int low, int high) {
    int pivot = array[high]; // Choix du pivot
    int i = low - 1; // Indice de l'élément plus petit

    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(&array[i], &array[j]); // Échanger les éléments
        }
    }
    swap(&array[i + 1], &array[high]); // Mettre le pivot à sa position correcte
    return i + 1;
}

// Fonction récursive Quicksort
void quicksort(int array[], int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high); // Index du pivot après partitionnement
        quicksort(array, low, pi - 1); // Trier les éléments avant le pivot
        quicksort(array, pi + 1, high); // Trier les éléments après le pivot
    }
}

// Fonction principale pour tester l'algorithme
int main() {
    int array[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(array) / sizeof(array[0]);

    printf("Tableau avant tri :\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    quicksort(array, 0, n - 1);

    printf("Tableau après tri :\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

Explication du code

Fonction swap :
La fonction permet d’échanger deux éléments dans le tableau. Elle est utilisée lors du partitionnement pour réorganiser les éléments.
Fonction partition :

Le pivot est choisi comme étant le dernier élément du tableau.
Un pointeur ((i)) est initialisé avant la limite inférieure ((low – 1)).
Chaque élément est comparé au pivot. Si un élément est inférieur ou égal au pivot, (i) est incrémenté et l’élément est échangé avec celui à la position (i).
Une fois le tableau parcouru, le pivot est placé à sa position correcte en l’échangeant avec l’élément à (i + 1).

Fonction quicksort :

Si le tableau à traiter a plus d’un élément ((low < high)), on appelle la fonction de partitionnement pour obtenir l’index du pivot.
La fonction est appelée récursivement pour les deux sous-tableaux créés par le pivot :
- Le sous-tableau gauche (éléments inférieurs au pivot).
- Le sous-tableau droit (éléments supérieurs au pivot).

Fonction main :

Déclare un tableau d’exemple.
Affiche le tableau avant et après le tri rapide pour illustrer les résultats.

Exécution et résultats

Entrée :

[ 10, 80, 30, 90, 40, 50, 70 ]

Sortie :

Avant tri : 10 80 30 90 40 50 70
Après tri : 10 30 40 50 70 80 90

Points importants à noter

Cette implémentation choisit toujours le dernier élément comme pivot. Une version optimisée pourrait utiliser des stratégies pour choisir un pivot plus efficace (par exemple, le pivot médian).
L’implémentation utilise des indices pour minimiser la consommation de mémoire, ce qui rend le Quicksort en C très performant pour les applications où l’efficacité est essentielle.
Le code peut être facilement adapté pour des tableaux de tailles ou de types différents.

Analyse de la complexité temporelle et spatiale

Complexité temporelle

La complexité temporelle de l’algorithme Quicksort dépend fortement de la manière dont le pivot est choisi et de la distribution des éléments dans le tableau. Voici les différents cas :

Meilleur cas :

Si le pivot divise le tableau en deux parties égales à chaque itération, le temps d’exécution est optimal.
À chaque niveau de récursion, (n) comparaisons sont effectuées, et il y a (O(\log n)) niveaux dans l’arbre de récursion.
Complexité : (O(n \log n)).

Cas moyen :

Même si le pivot ne divise pas toujours exactement en deux, le comportement général suit une tendance similaire au meilleur cas.
Cela est dû à une distribution moyenne des éléments autour du pivot.
Complexité : (O(n \log n)).

Pire cas :

Le pire cas se produit lorsque le pivot est toujours l’élément le plus petit ou le plus grand. Cela crée des divisions déséquilibrées, où l’un des sous-tableaux est vide.
Dans ce cas, l’algorithme effectue (n – 1), (n – 2), …, (1) comparaisons, ce qui correspond à une somme arithmétique.
Complexité : (O(n^2)).

Résumé des complexités temporelles

Cas	Complexité temporelle
Meilleur cas	(O(n \log n))
Cas moyen	(O(n \log n))
Pire cas	(O(n^2))

Complexité spatiale

Quicksort est connu pour son efficacité en termes d’espace mémoire :

Implémentation en place :

Dans la plupart des implémentations (comme celle présentée en C), Quicksort ne nécessite pas de tableau supplémentaire pour le tri.
La mémoire utilisée est principalement celle de la pile pour les appels récursifs.

Profondeur de la pile :

Dans le meilleur cas, la profondeur de récursion est (O(\log n)), correspondant à une division équilibrée du tableau.
Dans le pire cas, la profondeur atteint (O(n)), lorsque le tableau est divisé de manière déséquilibrée.

Cas	Complexité spatiale
Meilleur cas	(O(\log n))
Cas moyen	(O(\log n))
Pire cas	(O(n))

Optimisation pour éviter le pire cas

Choix du pivot :

Sélectionner le pivot comme élément médian ou utiliser une approche de « pivot aléatoire » pour réduire les risques de division déséquilibrée.

Limitation de la récursion :

Utiliser une version non récursive de Quicksort pour éviter les dépassements de la pile dans des cas extrêmes.

Passage à un autre algorithme :

Pour des sous-tableaux de petite taille, passer à un algorithme comme l’insertion sort, plus efficace pour ces cas.

Comparaison avec d’autres algorithmes de tri

Algorithme	Complexité moyenne	Complexité pire cas	Complexité spatiale	Type
Quicksort	(O(n \log n))	(O(n^2))	(O(\log n))	Diviser/régner
Merge Sort	(O(n \log n))	(O(n \log n))	(O(n))	Diviser/régner
Heap Sort	(O(n \log n))	(O(n \log n))	(O(1))	Basé sur un tas
Insertion Sort	(O(n^2))	(O(n^2))	(O(1))	Direct

Conclusion

Quicksort est un algorithme très performant dans la majorité des cas grâce à sa complexité moyenne en (O(n \log n)) et son utilisation efficace de la mémoire. Cependant, il est crucial d’optimiser le choix du pivot pour éviter le pire cas, qui peut dégrader considérablement les performances.

Cas pratiques et exercices d’application

Exemple pratique : Tri d’un tableau de nombres entiers

Imaginons un tableau non trié de nombres entiers :
[ 45, 12, 78, 4, 89, 23, 56, 10 ]

Étapes :

Choix du pivot : Supposons que le pivot est le dernier élément, ici (10).
Partitionnement : Réorganiser les éléments en plaçant ceux inférieurs à (10) à gauche et ceux supérieurs à droite. Résultat après le premier passage :
[ 4, 10, 78, 45, 89, 23, 56, 12 ].
Le pivot est à sa position finale ((10)).
Sous-tableaux :

Gauche ((4)) : déjà trié.
Droite ((78, 45, 89, 23, 56, 12)) : appliquer récursivement l’algorithme.

Résultat final : [ 4, 10, 12, 23, 45, 56, 78, 89 ].

Ce cas montre la puissance de Quicksort pour organiser efficacement les données.

Exercice 1 : Implémentation avec des nombres aléatoires

Objectif : Modifier le programme Quicksort pour trier un tableau de 20 entiers générés aléatoirement.

Instructions :

Utiliser la bibliothèque stdlib.h pour générer les nombres aléatoires.
Tester le programme pour vérifier que les résultats sont corrects.

Code modifié :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quicksort(int array[], int low, int high);
int partition(int array[], int low, int high);
void swap(int* a, int* b);

int main() {
    int n = 20;
    int array[n];
    srand(time(0));

    // Générer un tableau de nombres aléatoires
    printf("Tableau aléatoire :\n");
    for (int i = 0; i < n; i++) {
        array[i] = rand() % 100; // Génère des nombres entre 0 et 99
        printf("%d ", array[i]);
    }
    printf("\n");

    quicksort(array, 0, n - 1);

    printf("Tableau trié :\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

Exercice 2 : Tri des chaînes de caractères

Objectif : Modifier Quicksort pour trier un tableau de chaînes de caractères.

Instructions :

Remplacer le tableau d’entiers par un tableau de chaînes.
Utiliser la fonction strcmp pour comparer les chaînes.

Code suggéré :

#include <stdio.h>
#include <string.h>

void quicksort(char* array[], int low, int high);
int partition(char* array[], int low, int high);
void swap_strings(char** a, char** b);

int main() {
    char* array[] = {"orange", "apple", "banana", "grape", "pear"};
    int n = sizeof(array) / sizeof(array[0]);

    printf("Tableau avant tri :\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", array[i]);
    }
    printf("\n");

    quicksort(array, 0, n - 1);

    printf("Tableau trié :\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", array[i]);
    }
    printf("\n");

    return 0;
}

// Implémentation spécifique pour les chaînes
void swap_strings(char** a, char** b) {
    char* temp = *a;
    *a = *b;
    *b = temp;
}

int partition(char* array[], int low, int high) {
    char* pivot = array[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (strcmp(array[j], pivot) <= 0) {
            i++;
            swap_strings(&array[i], &array[j]);
        }
    }
    swap_strings(&array[i + 1], &array[high]);
    return i + 1;
}

void quicksort(char* array[], int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);
        quicksort(array, low, pi - 1);
        quicksort(array, pi + 1, high);
    }
}

Exercice 3 : Analyser la complexité expérimentale

Objectif : Mesurer le temps d’exécution de Quicksort sur des tableaux de tailles croissantes.

Instructions :

Utiliser la bibliothèque time.h pour mesurer le temps.
Tester pour des tailles (n = 1000, 10000, 100000).

Code de base pour mesurer le temps :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quicksort(int array[], int low, int high);
int partition(int array[], int low, int high);
void swap(int* a, int* b);

int main() {
    int n = 10000; // Taille du tableau
    int* array = malloc(n * sizeof(int));
    srand(time(0));

    for (int i = 0; i < n; i++) {
        array[i] = rand() % 100000; // Générer des nombres aléatoires
    }

    clock_t start = clock();
    quicksort(array, 0, n - 1);
    clock_t end = clock();

    printf("Temps d'exécution : %lf secondes\n", (double)(end - start) / CLOCKS_PER_SEC);

    free(array);
    return 0;
}

Conclusion

Ces exercices illustrent la flexibilité de Quicksort et son adaptation à différents scénarios. En pratiquant ces cas, vous développerez une compréhension approfondie de cet algorithme et apprendrez à le personnaliser pour divers besoins pratiques.

Conclusion

Dans cet article, nous avons exploré en détail l’algorithme Quicksort, un outil puissant et largement utilisé pour le tri des données. Nous avons présenté son fonctionnement, ses étapes clés, et son implémentation en C, accompagnés d’une analyse approfondie de sa complexité temporelle et spatiale.

Grâce à ses performances moyennes de (O(n \log n)) et à son faible coût en mémoire, Quicksort est souvent le choix privilégié dans de nombreuses applications pratiques. Cependant, son efficacité dépend du choix judicieux du pivot pour éviter les cas extrêmes où la complexité atteint (O(n^2)).

Les exemples pratiques et exercices proposés vous permettent de mettre en œuvre cet algorithme dans des contextes variés, comme le tri de nombres aléatoires ou de chaînes de caractères, tout en mesurant ses performances.

Maîtriser Quicksort vous offre une base solide pour aborder des projets nécessitant une gestion efficace des données, en combinant théorie et pratique pour un développement informatique robuste et performant.