Tri rapide et sélection du pivot
Construisez un tri rapide avec les schémas de partition de Lomuto et de Hoare, examinez le pire cas en O(n²) et découvrez comment la sélection aléatoire du pivot en limite les effets.
Tri rapide et sélection du pivot est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Tri rapide : diviser pour régner en place
Le tri rapide est l'algorithme de tri le plus utilisé en pratique. Contrairement au tri fusion, il trie en place sans allouer de tableaux supplémentaires. L'idée principale consiste à choisir un élément pivot, à effectuer une partition du tableau afin que tous les éléments inférieurs au pivot le précèdent et que tous les éléments supérieurs le suivent, puis à trier récursivement chaque partition. L'étape de partition prend un temps en O(n) et, avec un bon pivot, la profondeur de récursion est en O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Méthode de partition de Lomuto
La partition de Lomuto utilise le dernier élément comme pivot. Un pointeur lent i suit la limite de la région des éléments inférieurs au pivot ; un pointeur rapide j parcourt le tableau vers l'avant. Lorsque arr[j] <= pivot, incrémentez i et échangez arr[i] avec arr[j], ce qui agrandit la région des petits éléments. Après le parcours, placez le pivot en i+1 en l'échangeant avec arr[hi]. Cette méthode est simple à implémenter, mais effectue 3× plus d'échanges que la méthode de Hoare.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Méthode de partition de Hoare
La partition de Hoare utilise deux pointeurs partant des deux extrémités et progressant vers le centre jusqu'à ce qu'ils se croisent. Elle choisit le pivot (généralement le premier élément) et déplace les éléments inférieurs au pivot vers la gauche et les éléments supérieurs vers la droite. La méthode de Hoare effectue 3× moins d'échanges que celle de Lomuto et fonctionne mieux avec les éléments égaux, mais le pivot ne se trouve pas à sa position finale après la partition, ce qui nécessite des appels récursifs légèrement différents.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Pire cas O(n²) : entrée déjà triée
Le pire cas du tri rapide survient lorsque le pivot est systématiquement l'élément le plus petit ou le plus grand de la partition. Avec le pivot pris comme dernier élément dans la méthode de Lomuto, sur un tableau déjà trié, la partition place toujours 0 élément à gauche et n-1 à droite : l'arbre de récursion dégénère en une chaîne de profondeur n, ce qui donne O(n²) comparaisons. C'est pourquoi le choix du pivot est essentiel et pourquoi les implémentations destinées à la production choisissent le pivot aléatoirement.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Pivot aléatoire : O(n log n) attendu
En choisissant le pivot uniformément au hasard (échangez un élément aléatoire avec arr[hi] avant la partition), la probabilité de choisir systématiquement de mauvais pivots diminue de manière exponentielle. Le nombre attendu de comparaisons est 2n ln(n) ≈ 1.39 n log₂(n), ce qui donne un temps attendu en O(n log n) avec une probabilité écrasante. C'est pourquoi le tri rapide randomisé est utilisé en pratique : il évite les pires cas pathologiques qu'un adversaire pourrait construire pour des stratégies à pivot fixe.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Pivot médian de trois
Une autre stratégie de choix du pivot consiste à choisir la médiane du premier, du milieu et du dernier élément. Cela évite le comportement du pire cas sur les entrées triées ou triées en ordre inverse (les entrées adversariales les plus courantes), tout en évitant le coût de la génération de nombres aléatoires. De nombreuses implémentations de production utilisent la médiane de trois ou la médiane de trois médianes pour les grands tableaux et reviennent au tri par insertion pour les petits sous-tableaux de moins d'environ 10 éléments.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Drapeau national néerlandais : partition à trois voies
La partition standard place les éléments inférieurs au pivot à gauche et les éléments supérieurs à droite, mais les éléments égaux au pivot sont dispersés. Le partitionnement à trois voies (drapeau national néerlandais) crée trois régions : <pivot, ==pivot, >pivot. C'est essentiel pour les tableaux contenant de nombreux doublons : alors que le tri rapide standard se dégrade en O(n²), le tri rapide à trois voies donne O(n) pour les entrées dont toutes les valeurs sont identiques.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect : k-ième plus petit élément en O(n)
Quickselect utilise l'étape de partition du tri rapide pour trouver le k-ième plus petit élément en temps moyen O(n), sans effectuer un tri complet. Après la partition, le pivot se trouve à sa position finale p. Si p == k, renvoyez arr[p]. Si k < p, effectuez la récursion sur la partition de gauche ; si k > p, effectuez-la sur la partition de droite. En moyenne, chaque récursion divise le problème par deux : O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Complexité spatiale du tri rapide
On dit que le tri rapide s'effectue « en place », mais la récursion utilise en moyenne un espace de pile en O(log n) (une trame par niveau de l'arbre de récursion). Dans le pire cas, la profondeur de la pile est en O(n). Pour garantir un espace de pile en O(log n) dans le pire cas, effectuez toujours la récursion d'abord sur la plus petite partition et utilisez l'optimisation des appels terminaux pour la plus grande. La limite de récursion de Python rend risquées les récursions très profondes du tri rapide — un point à signaler lors des entretiens.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Comparer les algorithmes de tri
Faites la synthèse de vos connaissances :
- Tri rapide : O(n log n) attendu, O(n²) dans le pire cas, espace O(log n), non stable, le plus rapide en pratique pour les données aléatoires
- Tri fusion : O(n log n) garanti, espace O(n), stable, idéal pour les listes chaînées et le tri externe
- Tri par tas : O(n log n) garanti, espace O(1), non stable, plus lent en pratique à cause des défauts de cache
- Tri par insertion : meilleur cas en O(n), idéal pour les petites valeurs de n ou les données presque triées
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort : combiner les trois
Introsort (utilisé dans la STL C++ std::sort) combine le tri rapide, le tri par tas et le tri par insertion : commencez par un tri rapide randomisé ; si la profondeur de récursion dépasse 2 log n (ce qui indique une mauvaise suite de pivots), passez au tri par tas afin de garantir O(n log n) ; utilisez le tri par insertion pour les sous-tableaux de moins de 16 éléments. Vous obtenez ainsi un pire cas en O(n log n), la rapidité moyenne du tri rapide et l'efficacité du tri par insertion sur les petits sous-tableaux.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Vérification rapide
Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le tri rapide effectue une partition en place autour d'un pivot et applique récursivement le même traitement à chaque côté, ce qui permet d'obtenir un temps attendu en O(n log n) avec un espace de pile en O(log n) — plus rapidement en pratique que le tri fusion pour les données aléatoires, le pire cas O(n²) survient sur une entrée triée avec un pivot fixe et peut être évité par une sélection aléatoire du pivot ou par la médiane de trois, et le partitionnement à trois voies traite efficacement les doublons, tandis que Quickselect étend l'idée de partition pour trouver le k-ième plus petit élément en temps moyen O(n), sans effectuer de tri complet. Nous allons maintenant étudier les tris sans comparaison et la fonction sort intégrée de Python.
Questions Fréquemment Posées
La leçon « Tri rapide et sélection du pivot » est-elle gratuite ?
Oui — le texte complet de « Tri rapide et sélection du pivot » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tri rapide et sélection du pivot » ?
Construisez un tri rapide avec les schémas de partition de Lomuto et de Hoare, examinez le pire cas en O(n²) et découvrez comment la sélection aléatoire du pivot en limite les effets. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Tri rapide et sélection du pivot » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri à bulles et tri par insertion
- Tri fusion : diviser, trier, fusionner
- Tri rapide et sélection du pivot
- Tris sans comparaison et sort() de Python