date: 2023-10-16
Type: Cours
Projet: Blindcode
Cours: Algorithmie

Tri Rapide (Quicksort)

Header :

Le tri rapide, également connu sous le nom de Quicksort, est l'un des algorithmes de tri les plus efficaces et largement utilisés. Dans ce chapitre, nous allons explorer le fonctionnement du tri rapide et analyser sa complexité.

Body

12.1 Principe de Base

Le tri rapide est un algorithme de tri basé sur la stratégie de diviser pour régner. Il fonctionne en choisissant un élément pivot dans le tableau, puis en réorganisant les éléments du tableau de manière à ce que tous les éléments plus petits que le pivot soient à gauche, et tous les éléments plus grands que le pivot soient à droite. Ensuite, l'algorithme est appliqué récursivement aux deux sous-tableaux ainsi créés.

Voici un exemple de code en pseudo-code illustrant le tri rapide :

FONCTION triRapide(tableau : TABLEAU) : TABLEAU
    SI LONGUEUR(tableau) <= 1 ALORS
        RETOURNER tableau  // Cas de base
    SINON
        pivot <- CHOISIR_PIVOT(tableau)  // Choix du pivot (par exemple, le premier élément)
        INFÉRIEUR, ÉGAL, SUPÉRIEUR : TABLEAU <- PARTITIONNER(tableau, pivot)
        RETOURNER CONCATÉNER(triRapide(INFÉRIEUR), ÉGAL, triRapide(SUPÉRIEUR))
    FIN SI
FIN FONCTION

FONCTION PARTITIONNER(tableau : TABLEAU, pivot : ÉLÉMENT) : (TABLEAU, TABLEAU, TABLEAU)
    INFÉRIEUR, ÉGAL, SUPÉRIEUR : TABLEAU <- TABLEAU_VIDE, TABLEAU_VIDE, TABLEAU_VIDE
    POUR chaque élément DANS tableau FAIRE
        SI élément < pivot ALORS
            AJOUTER élément À INFÉRIEUR
        SINON SI élément = pivot ALORS
            AJOUTER élément À ÉGAL
        SINON
            AJOUTER élément À SUPÉRIEUR
        FIN SI
    FIN POUR
    RETOURNER (INFÉRIEUR, ÉGAL, SUPÉRIEUR)
FIN FONCTION

12.2 Complexité

La complexité temporelle du tri rapide dépend du choix du pivot et de la répartition des éléments. Dans le meilleur des cas, lorsque le pivot divise le tableau presque également à chaque étape, la complexité est en moyenne O(n log n). Dans le pire des cas, lorsque le pivot est toujours l'élément le plus petit ou le plus grand, la complexité peut devenir quadratique, soit O(n^2).

Cependant, en moyenne, le tri rapide est très efficace et il est souvent préféré pour trier de grandes quantités de données en raison de sa complexité O(n log n).

La complexité spatiale est généralement O(log n) en raison de la récursivité de l'algorithme.

12.3 Avantages et Limitations

Le tri rapide est un algorithme de tri performant pour de grandes quantités de données. Il est également utilisé comme algorithme de tri interne dans de nombreuses bibliothèques de programmation. Cependant, il a quelques limitations, notamment la possibilité d'avoir une mauvaise performance dans le pire des cas (quand le pivot est mal choisi) et d'être moins stable que d'autres algorithmes de tri (l'ordre relatif des éléments égaux peut ne pas être préservé).

Pour minimiser les inconvénients du tri rapide, des variantes et des stratégies d'optimisation ont été développées, telles que la sélection de pivots médians, la "méthode des trois médianes", et la détection de seuils pour basculer vers un tri plus efficace pour de petites tailles de tableau.