- def: statique d'ordre (statistic order) est le i-ème plus petit élément
- def: minimum i=1, max i=n
- def: mediane est le point central, lower median si pair
probleme : determiner l'ordre i-eme (selection problem)
- input: ensemble A d'elements distincts, 1 <= i <= n
- output: element x de A, plus large que exactement i-1 autres elements de A
Approche simple: O(n lg n), en triant l'ensemble, puis en prenant l'element i.
plan:
- 9.1: selection de min et max
- 9.2: algo en O(n) en temp attendu
- 9.3: algo en O(n) dans le pire des cas
minimum de comparaison nécessaire = n-1
algo:
min = A[1]
pour chaque x de A:
si min > x alors min = x
return x
preuve: moins de comparaisons -> au moins 1 element n'est pas testé. Si c'est le mac, alors fails
ex: points 2D, besoin de trouver les limites
algo:
2 comparaison par element
si n impaire -> prendre le premier element pour initialiser min et max. 3*|n/2| comparaisons
si n pair -> faire une premiere comparaison pour determiner min et max. 3*|n-2)/2 comparaisons
temps asymptotique: Theta(n). Par diviser-conquerir, basé sur quicksort
RANDOMIZED-SELECT sur 1 coté de la partition, ce qui fait passer de Theta(n lg n) à Theta(n).
RANDOMIZED-SELECT(A ,p, r, i)
si p==r
return A[p]
q = RANDOMIZED-PARTITION(A ,p, r)
k = q-p+1
si i == k: // pivot est le resultat
A[q]
sinon si i < k:
return RANDOMIZED-SELECT(A ,p, q-1, i)
sinon:
return RANDOMIZED-SELECT(A ,q+1, r, i-k)
Worst case: Theta(n^2), puisque partioning prend Theta(n)
demonstration via esperance statistique pour montrer que le cas moyen est en O(n)
algo:
partitionner en groups de 5 elements
trouver la mediane de chaque groupe apres insertion sort
utiliser SELECT pour trouver la mediane
partitionner a partir de la mediane trouvée
si i=k, retourner x. Sinon, utiliser SELECT recursivement