## Qu'est-ce que le tri rapide (QuickSort) ?

Le tri rapide (QuickSort) est un algorithme de tri efficace qui utilise une stratégie appelée "diviser pour régner". Il fonctionne en partitionnant le tableau en deux sous-tableaux autour d'un élément appelé pivot de manière à ce que tous les éléments inférieurs au pivot soient à sa gauche et ceux supérieurs soient à sa droite. Ensuite, l'algorithme applique récursivement la même stratégie aux sous-tableaux.

## Étapes de fonctionnement :

- Choisir un pivot : Un élément du tableau est choisi comme pivot (généralement le premier, le dernier, ou un élément aléatoire).

- Partitionner le tableau : Réarranger les éléments du tableau de manière à ce que :
    + Tous les éléments plus petits que le pivot soient à gauche,
    + Tous les éléments plus grands soient à droite.

- Appliquer récursivement le tri :
    + Répéter les étapes ci-dessus sur les sous-tableaux (gauche et droite) jusqu'à ce que la taille des sous-tableaux soit 1 ou 0.

Le tri rapide est efficace avec une complexité moyenne de O(n log n), mais dans le pire des cas (pivot mal choisi), sa complexité peut être O(n²).

## Exemple pas à pas

Imaginons le tableau suivant :
`[8, 3, 1, 7, 0, 10, 2]`

1. Choisir le pivot : Prenons 7 comme pivot.
2. Partitionner :
    + Les éléments < 7 : `[3, 1, 0, 2]`
    + Les éléments > 7 : `[8, 10]` 
    + Le pivot reste au milieu : `[3, 1, 0, 2, 7, 8, 10]`
3. Répéter récursivement :
    + Sous-tableau gauche `[3, 1, 0, 2]` : Pivot = 2, devient `[0, 1, 2, 3]`
    + Sous-tableau droit `[8, 10]` : Déjà trié.

Résultat final : `[0, 1, 2, 3, 7, 8, 10]`