Quick Sort
Dernière mise à jour
Le tri rapide est un algorithme diviser pour régner qui trie autour d'un « pivot ». Il choisit un élément pivot, puis partitionne le tableau de sorte que tout ce qui est plus petit vienne avant et tout ce qui est plus grand vienne après - ce qui verrouille le pivot dans sa position triée finale. Il applique ensuite la récursion sur les partitions gauche et droite. Cette visualisation utilise le schéma de Lomuto avec le dernier élément comme pivot. Appuyez sur lecture pour voir le partitionnement et le placement du pivot.
Le tri rapide est généralement le tri généraliste le plus rapide en pratique grâce à un bon comportement de cache et au partitionnement en place, avec une moyenne de O(n log n). Son pire cas est O(n²) (par exemple un tableau déjà trié avec un mauvais choix de pivot), que de bonnes stratégies de pivot comme la médiane de trois ou l'aléatoire évitent.
Complexité en temps et en espace
| Cas | Complexité | Notes |
|---|---|---|
| Meilleur cas | O(n log n) | Partitions équilibrées |
| Cas moyen | O(n log n) | Ordre aléatoire |
| Pire cas | O(n²) | Pivots systématiquement déséquilibrés |
| Espace | O(log n) | Pile de récursion (partitionnement en place) |
| Stable | Non | Les échanges du partitionnement réordonnent les éléments égaux |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Choisir un pivot (ici, le dernier élément de la plage). |
| 2 | Partitionner : déplacer à sa gauche tous les éléments plus petits que le pivot. |
| 3 | Échanger le pivot vers la frontière - il est maintenant à sa position finale. |
| 4 | Appliquer récursivement le tri rapide à la partition gauche. |
| 5 | Appliquer récursivement le tri rapide à la partition droite. |
Exemple résolu
Tri de [5, 2, 4, 1] avec le schéma de Lomuto (dernier élément comme pivot) :
| Passe | Tableau | Action |
|---|---|---|
| Début | [5, 2, 4, 1] | Partitionner toute la plage ; le pivot est 1 (dernier élément). |
| 1 | [1, 2, 4, 5] | Rien n'est plus petit que 1, on échange donc 1 vers l'indice 0 ; le pivot 1 est maintenant final. Récursion à droite sur [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Partitionner [2, 4, 5] avec le pivot 5 ; 2 et 4 sont tous deux plus petits, donc 5 reste à la fin et est final. Récursion à gauche sur [2, 4]. |
| 3 | [1, 2, 4, 5] | Partitionner [2, 4] avec le pivot 4 ; 2 est plus petit, donc 4 reste en place et est final. 2 est un élément unique, il est donc déjà trié. |
| Terminé | [1, 2, 4, 5] | Chaque pivot est verrouillé à sa place ; le tableau est trié. |
Quand utiliser le tri rapide
| À utiliser quand | À éviter quand |
|---|---|
| Vous avez besoin d'un tri en mémoire rapide et généraliste avec de petits facteurs constants. | Vous avez besoin d'un temps O(n log n) garanti au pire cas (utilisez le tri par tas ou le tri fusion). |
La mémoire est limitée - le partitionnement est en place et ne nécessite que O(log n) d'espace de pile. | Vous avez besoin d'un tri stable qui préserve l'ordre des clés égales. |
| Les données sont dans un ordre aléatoire ou inconnu et vous utilisez un pivot aléatoire ou médiane de trois. | L'entrée est déjà triée ou presque triée et le pivot est fixe, déclenchant O(n²). |
| La localité de cache compte, car le tri rapide accède à la mémoire de façon séquentielle. | Vous triez une liste chaînée, où le tri fusion évite l'accès aléatoire dont dépend le tri rapide. |
Code de Quick Sort
Une implémentation propre et exécutable de Quick Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Quick Sort en Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Code de Quick Sort en JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Code de Quick Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Code de Quick Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Code de Quick Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}FAQ sur le tri rapide
Quelle est la complexité temporelle du tri rapide ?
Le tri rapide a une moyenne de
O(n log n) et est en O(n log n) dans le meilleur cas, mais se dégrade en O(n²) au pire cas lorsque les partitions sont systématiquement déséquilibrées. Des pivots aléatoires ou médiane de trois rendent le pire cas très improbable.Le tri rapide est-il stable ?
Non. Le partitionnement standard en place échange des éléments distants, ce qui peut modifier l'ordre relatif des clés égales. Des variantes stables existent mais renoncent à l'avantage du tri rapide de travailler en place.
Pourquoi le tri rapide est-il souvent plus rapide que le tri fusion ?
Le tri rapide partitionne en place avec une excellente localité de cache et sans tampon supplémentaire, donc ses constantes sont petites. Le tri fusion atteint la même borne
O(n log n) mais paie un tampon O(n) et davantage de déplacements de données.Tri rapide ou tri fusion - lequel choisir ?
Choisissez le tri rapide pour trier rapidement et en place des tableaux en mémoire, où ses petites constantes l'emportent généralement. Choisissez le tri fusion lorsque vous avez besoin d'un tri stable, d'un pire cas
O(n log n) garanti, ou lorsque vous triez des listes chaînées ou des données externes qui ne tiennent pas en RAM.Pourquoi le tri rapide devient-il O(n²) sur un tableau trié ?
Avec un pivot fixe comme le premier ou le dernier élément, une entrée déjà triée fait que chaque partition ne sépare qu'un seul élément, produisant
n niveaux de récursion au lieu de log n. Choisir le pivot aléatoirement ou avec la médiane de trois brise ce schéma et rétablit le comportement O(n log n).Quelle est la différence entre les schémas de partitionnement de Lomuto et de Hoare ?
Le schéma de Lomuto utilise un seul indice qui parcourt de gauche à droite et est plus simple à coder, c'est pourquoi cette visualisation l'emploie. Le schéma de Hoare utilise deux pointeurs qui se déplacent vers l'intérieur et effectue généralement moins d'échanges, ce qui le rend plus rapide en pratique, mais il ne place pas le pivot à sa position finale pendant l'étape de partitionnement.
Ressources associées
Plus de visualisations
