Médiane des médianes

Un algorithme linéaire dans le pire des cas de calcul du Nieme plus grand élément d'un tableau a été publié par Blum, Floyd, Pratt, Rivest et Tarjan en 1973 dans "Time bounds for selection", parfois appelé BFPRT d'après les noms des auteurs. Il est basé sur l'algorithme de tri rapide et connu aussi comme algorithme de calcul de la médiane des médianes.

Bien que le tri rapide soit sous-quadratique en temps, en moyenne, il peut exiger un temps quadratique lorsque le choix du pivot est mauvais (prenons le cas d'un pivot égal au plus petit élément à chaque étape). La solution pour le rendre O(n log(n)) dans le pire des cas est de toujours trouver des "bons" pivots. Un bon pivot est celui pour lequel on peut établir qu'une proportion constante d'éléments situés au-dessous et au-dessus.

Algorithme

L'algorithme est 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).
• L'algorithme est alors appelée récursivement sur cette sous-liste de N/ 5 éléments pour trouver la vraie médiane de ces éléments.
• Enfin, la médiane des médianes est choisi pour être le pivot. Selon la position de l'élément recherche, l'algorithme recommence avec les éléments au dessus du pivot ou au dessous.

Propriétés du pivot

Le pivot choisi est à la fois inférieur à environ 3 (n/10) éléments et plus grand que 3 (n/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)

 T(n) ≤ T(n/5) + T(7n/10) + O(n)

D'où T(n) ≤ c*n*(1 + (9/10) + (9/10)² + ...) = O(n).

Remarque importante

Bien que cette approche fonctionne très bien en théorie, elle est souvent dépassée dans la pratique par l'algorithme utilisant des pivots aléatoires.

Notes et références