Determinarea medianei

Determinarea medianei

Mediana a n elemente este definita ca fiind acel element care este mai mic (sau egal) decat jumatate din elemente si este mai mare (sau egal) decat cealalta jumatate.

o      Spre exemplu mediana secventei 16, 12, 99, 95, 18, 87, 10 este 18 .

Problema aflarii medianei este corelata direct cu cea a sortarii deoarece, o metoda sigura de a determina mediana este urmatoarea:

o      Se sorteaza cele n elemente

o      Se extrage elementul din mijloc.

Tehnica partitionarii poate insa conduce la o metoda generala mai rapida, cu ajutorul careia se poate determina cel de-al  k-lea element ca valoare dintre n elemente.

o      Gasirea medianei reprezinta cazul special  k = n / 2 .

o      In acelasi context,  k = 1  precizeaza aflarea minimului, iar  k = n , aflarea maximului.

Algoritmul conceput de C.A.R. Hoare functioneaza dupa cum urmeaza.

o      Se presupune ca elementele avute in vedere sunt memorate in tabloul a cu dimensiunea n,

o      Pentru inceput se realizeaza o partitionare cu limitele s = 1, d = n si cu a[k] selectat pe post de pivot x.

o      In urma acestei partitionari rezulta valorile index i si j care satisfac relatiile [3.2.7.a].

1)x = a[k]

2)a[h] xpentru toti h < i

3)a[h] xpentru toti h > j [3.2.7.a]

4)i > j

o      Sunt posibile trei situatii:

1.     Valoarea pivotului x a fost prea mica, astfel incat limita dintre cele doua partitii este sub valoarea dorita k. Procesul de partitionare trebuie continuat pentru elementele a[i],,a[d] (partitia dreapta) (fig.3.2.7.a (a)).

2. Valoarea pivotului x a fost prea mare. Operatia de partitionare continua pentru partitia a[s],,a[j] (partitia stanga) (fig.3.2.7.a (b)).

3. j < k < i . In acest caz elementul a[k] separa tabloul in doua partitii, el desemnand mediana (fig.3.2.7.a (c)).

o      Procesul de partitionare se repeta pana la realizarea cazului 3.

(a)

s ji k d

(b)

s k ji d

(c)

s j k i d

Fig. 3.2.7.a. Determinarea medianei