Médiane des médianes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Médiane.

La Médiane des médianes est un algorithme pour trouver un élément dans une liste.

Un algorithme linéaire dans le pire des cas de calcul du N-ième plus grand élément d'un tableau a été publié par Blum, Floyd, Pratt (en), 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 sont situés en dessous du pivot (respectivement au-dessus).

Algorithme[modifier | modifier le code]

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

Propriétés du pivot[modifier | modifier le code]

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)[modifier | modifier le code]

T(n) ≤ T(n/5) + T(7n/10) + O(n), d'où T(n) ≤ c×n×(1 + (9/10) + (9/10)2 + ...) = O(n).

Remarque importante[modifier | modifier le code]

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.

Références[modifier | modifier le code]

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