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.
Médiane des médianes
Problème lié Algorithme de sélection
Structure des données Tableau
Temps d'exécution pire-cas
Complexité algorithmique spatiale en place

La médiane des médianes est un algorithme de sélection basé sur l'algorithme Quickselect pour trouver le kième élément le plus grand au sein d'une liste non triée. 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.

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 dans le pire cas, bien que cette technique soit en moyenne moins efficace que le choix d'un pivot aléatoire (qui évite le surcoût du calcul du pivot).

Principe général de l'algorithme[modifier | modifier le code]

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[1]).
  • L'algorithme est alors appelé récursivement sur cette sous-liste de é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 30ième et le 70ième 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[modifier | modifier le code]

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

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

  • le facteur est la recherche de la médiane parmi les médianes de quintuplet.
  • le facteur est le coût du travail de partitionnement autour du pivot.
  • le facteur est l'appel récursif (dans le pire cas) pour trouver le kième élément dans la partition correspondante.

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

Remarque importante[modifier | modifier le code]

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

Histoire[modifier | modifier le code]

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 noms des auteurs.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Modèle:Introduction to Algorithms
  2. (en) M. Blum, R. W. Floyd, V. Pratt, R. Rivest et R. Tarjan, « Time bounds for selection », J. Comput. System Sci., vol. 7,‎ , p. 448-461