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[1]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps

Pire cas	${\displaystyle O(n)}$
Meilleur cas	${\displaystyle O(n)}$

Complexité en espace

Pire cas	${\displaystyle O(\log n)}$

modifier - modifier le code - modifier Wikidata

En informatique, la médiane des médianes est un algorithme de sélection pour trouver le k-ième élément le plus grand au sein d'un tableau initialement 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 de la médiane des médianes fut publié par Blum, Floyd, Pratt (en), Rivest et Tarjan en 1973 dans Time bounds for selection[2], et est parfois appelé BFPRT d'après les initiales des noms des auteurs.

Principe général de l'algorithme

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

1. Calcul des médianes. L'algorithme divise le tableau 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[3]). On obtient alors une sous-liste constituée de ces ${\displaystyle n/5}$ médianes.
2. Calcul de la médiane des médianes. L'algorithme est appelé récursivement sur cette sous-liste de ${\displaystyle n/5}$ éléments pour trouver la vraie médiane de ces éléments, que l'on appelle la médiane des médianes. On peut alors garantir que l'élément obtenu se place entre le 30e et le 70e centile.
3. Appels récursifs. 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.

Exemple d'exécution

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

Étape 1

Commençons par faire des paquets de cinq :

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

que l'on visualise verticalement dans le tableau suivant :

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

Trions ensuite chaque paquets afin de récupérer les médianes de chacun d'eux (qui se trouvent sur la troisième ligne) :

	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

Étape 2

Le calcul de la médiane des médianes se fait récursivement en appelant l'algorithme sur la liste des médianes :

	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

Étape 3

Finalement, on appelle récursivement sur les éléments plus petit que 47 (en gris) si l'on sait que le k-ième élément est là, ou sur les éléments plus grand que 47.

	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

Propriétés du pivot

Parmi les ${\displaystyle n/5}$ groupes, la moitié ont leur médiane en dessous du pivot (la médiane des médianes), ce qui garantit au moins ${\displaystyle 3n/10}$ éléments en dessous du pivot (3 parmi chacun des ${\displaystyle n/10}$ groupes). Ainsi, le pivot choisi est à la fois inférieur à environ ${\displaystyle 3n/10}$ éléments et plus grand que ${\displaystyle 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.

Algorithme en temps linéaire

Dans cette section, nous montrons que l'algorithme est en temps linéaire en le nombre d'éléments, c'est-à-dire que le nombre d'étapes réalisées par l'algorithme est un ${\displaystyle O(n)}$ où ${\displaystyle n}$ est le nombre d'éléments dans la liste. On note ${\displaystyle T(n)}$ le temps d’exécution de l'algorithme sur une entrée de taille ${\displaystyle n}$. On a la récurrence suivante :

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

où

• le terme ${\displaystyle T(n/5)}$ est la recherche de la médiane parmi les ${\displaystyle n/5}$ médianes de quintuplet.
• le terme ${\displaystyle c\cdot n}$ est le coût du travail de calcul de la sous-liste des ${\displaystyle n/5}$ médianes, ainsi que le coût de partitionnement autour du pivot.
• le terme ${\displaystyle T(7n/10)}$ est le coût de l'appel récursif (dans le pire cas) pour trouver le k-ième élément dans la partition correspondante.

De cette formule on vérifie par récurrence sur ${\displaystyle n}$ :

${\displaystyle T(n)\leq 10\cdot c\cdot n}$

Ainsi ${\displaystyle T(n)}$ est un ${\displaystyle 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 ${\displaystyle 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.

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).

Notes et références

1. (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9).
2. (en) M. Blum, R. W. Floyd, V. Pratt, R. Rivest et R. Tarjan, « Time bounds for selection », J. Comput. System Sci., vol. 7,‎ 1973, p. 448-461
3. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press, 2009, 3^e éd. [détail de l’édition]