Médiane des médianes

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[2]).
• L'algorithme est alors appelé récursivement sur cette sous-liste de ${\displaystyle 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.

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. Pour visualiser :

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

Avec ${\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 partitionnement autour du pivot.
• le terme ${\displaystyle 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 on vérifie simplement par récurrence :

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

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.

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[3], et est parfois appelé BFPRT d'après les noms des auteurs.

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