Médiane des médianes

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps

Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(\log n)$

La médiane des médianes est un algorithme de sélection pour trouver le kième élément le plus grand au sein d'une liste non triée. Il est basé sur l'algorithme Quickselect. Cet algorithme est optimal dans le pire cas, avec une complexité en temps linéaire. La brique de base de l'algorithme est la sélection d'une médiane approchée en temps linéaire. L'algorithme est parfois appelé BFPRT d'après les noms des auteurs : Blum, Floyd, Pratt (en), Rivest et Tarjan.

Principe général de l'algorithme

L'algorithme se déroule en 3 étapes :

• L'algorithme divise la liste en groupes de cinq éléments. Ensuite, pour chaque groupe de cinq, la médiane est calculée (une opération qui peut s'effectuer en temps constant, par exemple en utilisant un algorithme de tri).
• L'algorithme est alors appelé récursivement sur cette sous-liste de $n/5$ éléments pour trouver la vraie médiane de ces éléments. On peut alors garantir que l'élément obtenu se place entre le 30e et le 70e centile.
• Enfin, la médiane des médianes est choisie pour être le pivot. Selon la position de l'élément recherché, l'algorithme recommence avec les éléments au-dessus du pivot ou en dessous, qui représentent au plus 70 % de la taille initiale de l'espace de recherche.

Propriétés du pivot

Parmi les $n/5$ groupes, la moitié ont leur médiane en dessous du pivot (la médiane des médianes), ce qui garantit au moins $3n/10$ éléments en dessous du pivot (3 parmi chacun des $n/10$ groupes). Ainsi, le pivot choisi est à la fois inférieur à environ $3n/10$ éléments et plus grand que $3n/10$ éléments. Ainsi, la médiane divise les éléments choisis quelque part entre ^30 %⁄_70 % et ^70 %⁄_30 %, ce qui assure dans le pire des cas un comportement linéaire de l'algorithme. Pour visualiser :

Une itération des deux premières étapes de l'algorithme sur {0,1,2,3,...99}

	12		15		11		2		9		5		0		7		3		21		44		40		1		18		20		32		19		35		37		39
	13		16		14		8		10		26		6		33		4		27		49		46		52		25		51		34		43		56		72		79
Médianes	17		23		24		28		29		30		31		36		42		47		50		55		58		60		63		65		66		67		81		83
	22		45		38		53		61		41		62		82		54		48		59		57		71		78		64		80		70		76		85		87
	96		95		94		86		89		69		68		97		73		92		74		88		99		84		75		90		77		93		98		91

En rouge, la médiane des médianes.

Preuve du O(n)

Avec $T(n)$ le temps d’exécution de l'algorithme sur une entrée de taille $n$, on a la récurrence suivante:

$T(n)\leq T(n/5)+T(7n/10)+c\cdot n$

où

• le facteur $T(n/5)$ est la recherche de la médiane parmi les $n/5$ médianes de quintuplet.
• le facteur $c\cdot n$ est le coût du travail de partitionnement autour du pivot.
• le facteur $T(7n/10)$ est l'appel récursif (dans le pire cas) pour trouver le ke élément dans la partition correspondante.

De cette formule de récurrence on vérifie simplement par induction:

$T(n)\leq 10\cdot c\cdot n\in O(n).$

Autres usages de la médiane

La sélection d'une médiane approchée en temps linéaire peut aussi être utilisée pour garantir au tri rapide une complexité en $O(n\log n)$ dans le pire cas. Dans les deux cas, l'utilisation de la médiane est en moyenne moins efficace que le choix d'un pivot aléatoire, qui évite le surcoût du calcul du pivot.

Histoire

L'algorithme de la médiane des médianes fut publié par Blum, Floyd, Pratt (en), Rivest et Tarjan en 1973 dans Time bounds for selection, et est parfois appelé BFPRT d'après les noms des auteurs.

Voir aussi

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Selection algorithm » (voir la liste des auteurs).