How it works?

Le tri rapide (Quick Sort) suit trois étapes : choisir un pivot, partitionner et appliquer la récursion.

Processus étape par étape :

1. Choisir un pivot : choisissez un élément comme pivot. Dans ce cours, nous utilisons toujours le dernier élément.
2. Partitionner : parcourez les autres éléments et divisez-les en ceux inférieurs au pivot et ceux supérieurs ou égaux à celui-ci.
3. Récurrence : triez le plus petit groupe et le plus grand groupe de la même manière, puis rassemblez-les sous la forme sorted-smaller + pivot + sorted-larger.

Exemple sur [7, 2, 9, 4] :

• Le pivot est 4 (le dernier élément). Partitionnez le reste [7, 2, 9] : les éléments inférieurs à 4 sont [2], le reste est [7, 9].
• Triez [2] (déjà trié) et triez [7, 9] (pivot 9, donne [7, 9]).
• Combinez : [2] + [4] + [7, 9] = [2, 4, 7, 9].