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é. 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, Rivest et Tarjan en 1973 dans Time bounds for selection, 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 : 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). On obtient alors une sous-liste constituée de ces médianes. Calcul de la médiane des médianes. L'algorithme est appelé récursivement sur cette sous-liste de é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. 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 3912 23 24 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 7917 16 14 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 8396 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 8722 95 94 86 89 69 68 97 73 92 74 88 99 84 75 90 77 93 98 91 Trions ensuite chaque paquet 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 3913 16 14 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 79 Médianes17 23 24 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 8322 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 8796 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 3913 16 14 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 79 Médianes17 23 24 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 8322 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 8796 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 petits que 47 (en gris) si l'on sait que le k-ième élément est là, ou sur les éléments plus grands que 47. 12 15 11 2 9 5 0 7 3 21 44 40 1 18 20 32 19 35 37 3913 16 14 8 10 26 6 33 4 27 49 46 52 25 51 34 43 56 72 79 Médianes17 23 24 28 29 30 31 36 42 47 50 55 58 60 63 65 66 67 81 8322 45 38 53 61 41 62 82 54 48 59 57 71 78 64 80 70 76 85 8796 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 groupes, la moitié ont leur médiane en dessous du pivot (la médiane des médianes), ce qui garantit 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 et , 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 où est le nombre d'éléments dans la liste. On note le temps d’exécution de l'algorithme sur une entrée de taille . On a la récurrence suivante :

où le terme est la recherche de la médiane parmi les médianes de quintuplet. le terme est le coût du travail de calcul de la sous-liste des médianes, ainsi que le coût de partitionnement autour du pivot. le terme 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 :

Ainsi est un

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

Notes et références

Catégorie:Algorithme