backend / algorithmes-structures-donnees
Algorithmes randomisés : quickselect randomisé
Explication
Ce que vous allez apprendre
- Expliquer pourquoi trouver le k-ième plus petit élément ne nécessite pas de trier tout le tableau
- Adapter le partitionnement de quicksort à quickselect en n'explorant qu'une seule des deux moitiés
- Justifier pourquoi quickselect atteint O(n) en moyenne alors que quicksort reste en O(n log n)
- Identifier le risque du pivot fixe (pire cas quadratique, exploitable par un attaquant) et le corriger par un pivot aléatoire
- Relier quickselect à des cas d'usage réels comme le calcul de médiane ou de percentile sur de grands volumes de données
Dans quel contexte ?
Un tableau de bord de monitoring doit calculer en temps réel le 95e percentile du temps de réponse d'une API, à partir de dizaines de milliers de mesures collectées chaque minute. Trier entièrement ces mesures pour ne lire qu'une seule valeur serait un gaspillage : O(n log n) pour une information qui ne nécessite que O(n) en moyenne. Quickselect calcule directement ce percentile, sans jamais trier l'intégralité des données, ce qui permet au tableau de bord de rester réactif même sous forte charge.
D'abord, le problème à résoudre : le k-ième plus petit élément
Trouver la médiane d'un tableau ne nécessite pas de le trier entièrement, ce qui coûterait O(n log n). Il doit exister une méthode plus directe pour répondre uniquement à cette question précise.
Prérequis
Cette leçon suppose acquis le partitionnement de quicksort (leçon 7) : quickselect en reprend exactement le mécanisme, mais ne récurse plus que sur une seule moitié.
Étape 1 : réutiliser une idée déjà connue, le partitionnement
Quickselect s'inspire du partitionnement de quicksort, vu plusieurs leçons plus tôt : réorganiser le tableau autour d'un pivot pour placer un élément à sa position finale.
Ce qui change par rapport à quicksort
Contrairement à quicksort, qui trie récursivement les deux moitiés, quickselect ne s'intéresse qu'à la portion du tableau qui contient réellement l'élément recherché, en ignorant complètement l'autre moitié.
| Algorithme | Objectif | Complexité moyenne | Complexité pire cas |
|---|---|---|---|
| Tri complet puis indexation | Trouver le k-ième élément | O(n log n) | O(n log n) |
| Quickselect (pivot fixe) | Trouver le k-ième élément | O(n) | O(n²) |
| Quickselect (pivot aléatoire) | Trouver le k-ième élément | O(n) | O(n²), extrêmement improbable |
Pourquoi cette différence donne une meilleure complexité
Cette élimination systématique d'une moitié du travail à chaque étape donne, en moyenne, une complexité linéaire O(n), bien mieux qu'un tri complet.
Un piège hérité de quicksort : le pivot fixe
Si le pivot est toujours choisi au même endroit, par exemple le dernier élément, un tableau déjà trié fait dégénérer chaque partition en une seule case retirée à la fois — le pire cas possible, quadratique.
Pourquoi ce piège est même exploitable
Un attaquant connaissant l'algorithme pourrait construire une entrée expressément pour provoquer ce ralentissement, un vrai risque dans un contexte adversarial.
Piège fréquent
Un pivot toujours choisi au même endroit rend l'algorithme vulnérable à une entrée construite exprès pour le ralentir — un vrai risque pour une API publique qui accepte des données non fiables. Un pivot aléatoire élimine ce risque en rendant le pire cas extrêmement improbable, plutôt que de dépendre de la donnée d'entrée.
La solution : introduire volontairement du hasard
En choisissant le pivot au hasard à chaque étape, aucune donnée d'entrée particulière ne peut systématiquement provoquer le pire cas : celui-ci devient possible mais extraordinairement improbable.
Ce que garantit exactement cette solution
C'est une garantie statistique plutôt qu'absolue, mais suffisamment forte pour être utilisée en toute confiance dans des bibliothèques de production.
Pour conclure ce parcours
Du simple tableau jusqu'à cet algorithme randomisé, l'idée centrale reste la même : comprendre la structure réelle d'un problème permet presque toujours de trouver une solution bien plus rapide que l'approche la plus évidente.
Commandes & code
Algorithmes randomisés : quickselect randomisé
Un pivot choisi au hasard élimine le pire cas déterministe O(n²) sur des entrées adverses ou déjà triées.
import random
def partition_randomisee(tableau: list[int], gauche: int, droite: int) -> int:
indice_pivot = random.randint(gauche, droite)
tableau[indice_pivot], tableau[droite] = tableau[droite], tableau[indice_pivot]
pivot = tableau[droite]
i = gauche - 1
for j in range(gauche, droite):
if tableau[j] <= pivot:
i += 1
tableau[i], tableau[j] = tableau[j], tableau[i]
tableau[i + 1], tableau[droite] = tableau[droite], tableau[i + 1]
return i + 1
def quickselect(tableau: list[int], k: int) -> int:
# Trouve le k-ième plus petit élément (k=0 -> minimum), sans trier tout le tableau
# Espérance O(n) grâce au pivot aléatoire, contre O(n log n) pour un tri complet
tableau = list(tableau)
gauche, droite = 0, len(tableau) - 1
while True:
if gauche == droite:
return tableau[gauche]
indice_pivot = partition_randomisee(tableau, gauche, droite)
if k == indice_pivot:
return tableau[k]
elif k < indice_pivot:
droite = indice_pivot - 1 # ne recurse que sur la partie contenant k, jamais les deux
else:
gauche = indice_pivot + 1
donnees = [7, 10, 4, 3, 20, 15]
assert quickselect(donnees, 0) == 3
assert quickselect(donnees, len(donnees) - 1) == 20
assert quickselect(donnees, 2) == sorted(donnees)[2]
def mediane(tableau: list[int]) -> float:
n = len(tableau)
if n % 2 == 1:
return float(quickselect(tableau, n // 2))
return (quickselect(tableau, n // 2 - 1) + quickselect(tableau, n // 2)) / 2
assert mediane([5, 3, 8, 1, 9, 2]) == 4.0
# Pourquoi le pivot aléatoire compte : un pivot FIXE (ex: toujours le dernier élément) dégénère
# en O(n^2) sur un tableau déjà trié -- un pivot aléatoire rend ce pire cas exponentiellement improbable
def compter_comparaisons_pivot_fixe(n: int) -> int:
tableau = list(range(n)) # déjà trié -- pire cas pour un pivot fixe en dernière position
comparaisons = [0]
def partition_fixe(t, g, d):
pivot = t[d]
i = g - 1
for j in range(g, d):
comparaisons[0] += 1
if t[j] <= pivot:
i += 1
t[i], t[j] = t[j], t[i]
t[i + 1], t[d] = t[d], t[i + 1]
return i + 1
def qs(t, g, d):
if g < d:
p = partition_fixe(t, g, d)
qs(t, g, p - 1)
qs(t, p + 1, d)
qs(tableau, 0, n - 1)
return comparaisons[0]
assert compter_comparaisons_pivot_fixe(100) == 100 * 99 // 2 # O(n^2) confirmé sur données triées
# --- Randomized QuickSort : la même idée appliquée au tri complet ---
def quicksort_randomise(tableau: list[int]) -> list[int]:
tableau = list(tableau)
def trier(g, d):
if g < d:
p = partition_randomisee(tableau, g, d)
trier(g, p - 1)
trier(p + 1, d)
trier(0, len(tableau) - 1)
return tableau
assert quicksort_randomise([5, 2, 9, 1, 5, 6]) == [1, 2, 5, 5, 6, 9]Résumé
- Le pivot aléatoire transforme un pire cas déterministe (données triées, adversaire connaissant l'algorithme) en un cas quasi impossible à provoquer.
quickselectne recurse que sur la moitié contenant l'élément cherché : espérance O(n), contre O(n log n) pour trier puis indexer.- La médiane s'obtient en deux appels à
quickselect(ou un seul si n est impair), sans jamais trier tout le tableau. quicksort_randomiseapplique le même principe de partition au tri complet, avec une espérance O(n log n) garantie indépendamment de l'ordre initial des données.
Exercices pratiques
Mission : sécuriser le calcul de percentile d'une API publique
Objectif : Diagnostiquer une vulnérabilité de pivot fixe dans quickselect et la corriger avec un pivot aléatoire.
Contexte
Un tableau de bord de monitoring expose une API publique qui accepte des listes de mesures de latence et calcule leur médiane via un quickselect dont le pivot est TOUJOURS le dernier élément du sous-tableau (comme dans compter_comparaisons_pivot_fixe). Un chercheur en sécurité signale qu'il peut faire ramer le service en envoyant des listes déjà triées, même avec seulement quelques milliers de mesures.