Sortarea prin
interclasare (merge sort)
Aceasta metoda de ordonare are la baza interclasarea
a doi vectori: fiind dati doi vectori ordonati se obtine un al treilea vector
ordonat care va contine elementele din cei doi vectori.
In cazul sortarii prin interclasare vectorii care
se interclaseaza sunt doua secvente ordonate din acelasi vector
Sortarea prin interclasare utilizeaza metoda
Divide et Impera:
-se imparte vectorul in secvente din ce in ce mai
mici., astfel incat fiecare secventa sa fie ordonata la un moment dat si
interclasata cu o alta secventa din vector corespunzatoare.
-practic interclasarea va incepe cand se ajunge
la o secventa formata din doua elemente. Aceasta odata ordonata se va
interclasa cu o alta corespunzatoare. Cele doua secvente vor alcatui in subsir
ordonat din vector mai mare care la randul lui se va interclasa cu subsirul
corespunzator samd.
Fie vectorul:
|
8 |
7 |
9 |
3 |
6 |
4 |
17 |
16 |
Se imparte in doua secvente:
|
8 |
7 |
9 |
3 |
6 |
4 |
17 |
16 |
In continuare pt prima secvente se procedeaza la
fel:
|
8 |
7 |
9 |
3 |
Dupa o noua impartire se obtine:
|
8 |
7 |
Se incepe interclasarea. Se considera ca avem
doi vectori de lungime 1 care se interclaseaza:
|
8 |
7 |
Rezulta:
|
7 |
8 |
La fel si pentru secventa :
|
9 |
3 |
Se considera ca avem
iar doi vectori de lungime 1 care se interclaseaza:
|
9 |
3 |
Rezulta:
|
3 |
9 |
Ceea ce inseamna ca cele doua secvente determina obtinerea urmatorului
subsir din vector:
|
7 |
8 |
3 |
9 |
Pentru care se interclaseaza cele doua zone. Rezulta:
|
3 |
7 |
8 |
9 |
La fel se procedeaza si cu secventa:
|
6 |
4 |
17 |
16 |
Se obtine:
|
6 |
4 |
Care se interclaseaza si se
obtine:
|
4 |
6 |
La fel pentru:
|
17 |
16 |
Se obtine:
|
16 |
17 |
Se obtine o noua secventa:
|
4 |
6 |
16 |
17 |
Care prin interclasarea celor doua zone conduce la:
|
4 |
6 |
16 |
17 |
Cele doua secvente initiale din vector au devenit:
|
3 |
7 |
8 |
9 |
4 |
6 |
16 |
17 |
Care se interclaseaza obtinand:
|
3 |
4 |
6 |
7 |
8 |
9 |
16 |
17 |
O solutie de implementare:
int a[1000],n;
void interclas(int i,int m,int j)
{int b[1000];
int x=i;
int k=1;
int y=m+1;
while(x<=m && y<=j)
if (a[x]<a[y])
b[k++]=a[x++];
else
b[k++]=a[y++];
while (x<=m)
b[k++]=a[x++];
while (y<=j)
b[k++]=a[y++];
int t=i;
for (k=1;k<=(j-i)+1;k++)
a[t++]=b[k];
}
void divimp(int i,int j)
{if (i<j)
{int m=(i+j)/2;
divimp(i,m);
divimp(m+1,j);
interclas(i,m,j);}
}
void main()
{clrscr();
cout<<"n=";
cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
divimp(1,n);
for(i=1;i<=n;i++)
cout<<a[i]<<' ';
getch();
}
Pentru a stabili complexitatea algoritmului de sortare prin
interclasare, remărcam urmatoarele:
- pentru un tablou cu n
elemente, numărul de înjumătățiri succesive până se ajunge la zone de lungime 1
sau 2 este de aproximativ log2n;
- la fiecare din aceste divizări
succesive, se mută din tab în tab1 și invers în total n elemente.
In consecinta, numarul de operatii elementare executate este de ordinul
O(n.log(n)).
Mai riguros, daca notam cu C(n)
numarul de operații elementare pentru sortarea unui tablou cu n componente și
avem în vedere că, la fiecare pas al algoritmului, se fac doua invocări
recursive ale metodei de sortare și o interclasare, iar interclasarea are
complexitatea n, atunci
C(n) = 2.C(n/2)+n
C(n) = 2(2C(n/4)+n/2)+n = 4C(n/4) + n + n
Algoritmul se oprește după log2(n) astfel de pași, când se obține
C(n) = nC(n/n) + n + n + ... + n = n.log2(n)
In consecință, complexitatea algoritmului de sortare prin interclasare
este O(n.log2(n)).
Constatăm deci că, pentru
tablouri cu numar mare de componente, timpul de calcul este mult mai mic în
cazul sortării prin interclasare, decât în cazul folosirii algoritmilor simpli,
cum ar fi cel al selecției, inserției sau al bulelor, a căror complexitate este
O(n2). Algoritmul de sortare prin interclasare consumă însă de două
ori mai multă memorie decât cei simpli mentionați, deoarece necesită spațiu
suplimentar pentru tabloul auxiliar .