#algorithme #code

Quicksort est un des meilleurs algorithmes de tri. Il a de meilleures performances que [[2023-07-15 Insertion Sort|Insertion Sort]] et que Sélection Sort, et n’a pas besoin de mémoire supplémentaire, comme [[2023-07-17 Merge Sort|Merge Sort]].

Quicksort a un average case en O(nlog(n)), lorsque l’array est aléatoire. Son worst-case arrive si l’array est déjà trié, et dans ce cas il est O(n^2) (il est donc conseillé de Shuffle l’array avant de faire un Quicksort). Il est O(n) en espace.

Pour faire un Quicksort : 1. Choisir le dernier élément l’array comme pivot 2. Pour chaque élément de l’array, le comparer au pivot. Si c’est plus petit ou égal, placer à gauche. Sinon placer à droite. (Bien garder les indexes de séparation de chaque partition) 3. Appliquer Quicksort récursivement sur chaque partition (gauche et droite)