Sortarea prin interclasareSortarea prin interclasare

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.

În 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 sortate. Aceasta odata ordonata, se va interclasa cu o alta corespunzatoare. Cele doua secvente vor alcătui un subsir ordonat din vector mai mare care la rândul lui se va interclasa cu subsirul corespunzator s.a.m.d.

Fie vectorul:

 8 7 9 3 6 4 17 16

la care n=8.  Se imparte in doua secvente (1+n)/2=(1+8)/2=4,5 şi se ia mijlocul ca fiind 4:

 8 7 9 3 6 4 17 16

In continuare pentru prima secvenţă se procedează la fel. Se împarte vectorul ce are 4 elemente în doi vectori de câte 2 elemente:

8 7 9 3

După o nouă împărţire se obţine:

 8 7 Fiindcă este o secvenţă de două elemente (q-p<=1), elementele din acest vector de două elemente se sortează:

 8 7

 Rezulta:

 7 8

 9 3

La fel si pentru secventa :

9 3

  Se considera ca avem un vector cu două elemente care se sortează între ele:

 9 3

 Rezultă:

 3 9

Cele doua secvente

 7 8 3 9

determina obtinerea urmatorului subsir din vector. Cele două secvenţe de câte doi vectori se interclasează. Rezulta:

 3 7 8 9

adică un subşir sortat.

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

 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

#include<iostream.h>int a[20],n;

Se declară ca variabile globale vectorul a[20] şi n – ce păstrează numărul de elemente din vector.

ProgramulProgramul

void sort(int p,int q) { if(a[p]>a[q]) { int aux=a[p]; a[p]=a[q]; a[q]=aux; } }

Se foloseşte o variabilă aux (pentru interschimbarea conţinutului celor două elemente). Ea are doi parametrii întregi p – pentru primul element al vectorului şi q pentru ultimul element al vectorului

Funcţia care sortează două elemente ale vectorului.

Funcţia care sortează două elemente ale vectorului.

Functia de interclasareFunctia de interclasare

void intercl(int p, int q, int m) { int b[20],i,j,k; i=p;j=m+1;k=0;

Funcţia de interclasare are trei parametri. p şi q sunt pentru primul respectiv ultimul element din vector iar m este mijlocul m=(p+q)/2

Functia de interclasareFunctia de interclasarewhile(i<=m&&j<=q) if(a[i]<a[j])

{ k++; b[k]=a[i]; i++;}

else{ k++; b[k]=a[j]; j++;}

Urmează procedura de interclasare cunoscută de la interclasarea a doi vectori. Se consideră ca prima jumatate a vectorului este primul vector (de la i=p la m) şi a doua jumatate a vectorului este al doilea vector (de la j=m+1 la q).

if(i<=m) for(int l=i;l<=m;l++) {

k++;b[k]=a[l];

}

Se copie în vectorul b elemente din prima jumătate a vectorului a.

Functia de interclasareFunctia de interclasare

else for(int l=j;l<=q;l++)

{ k++; b[k]=a[l];}

se copie în vectorul b elemente din a doua jumătate a vectorului a.

Functia de interclasareFunctia de interclasare

Functia de interclasareFunctia de interclasare

k=1; for(int l=p;l<=q;l++) { a[l]=b[k]; k++; }

se copie din vectorul b în vectorul a din nou, vectorul interclasat.

Functia divideFunctia divide

void divide(int p, int q) { int m; if(q-p<=1) sort(p,q); else { m=(p+q)/2; divide(p,m); divide(m+1,q); intercl(p,q,m); } }

În funcţia divide ce are doi parametri (p şi q pentru primul si ultimul element din vector). Se mai foloseşte o variabilă m pentru a afla mijlocul m=(p+q)/2. Dacă vectorul este format din două elemente, ele pot fi sortate (if(q-p)<=1 sort(p,q))În caz contrar, se calculează mijlocul, şi se apelează funcţia divide pentru prima jumatate a vectorului (divide(p,m)) şi pentru a doua jumatate (divide(m+1,q)). Dacă în urma aplicării acestei funcţii, rezultă vectori care au mai mult de 2 elemente, se imparte din nou vectorul în două până se va ajunge la vectori de 2 elemente care vor putea fi sortaţi. După ce se ajunge la această etapă, se parcurge drumul invers şi se interclasează vectorii rezultati în urma divizării până se va ajunge la interclasarea dintre cele două prime jumătăţi de vector.

Programul principalProgramul principal

int main(void){

int n,i;cout<<"n=";cin>>n;

for(int i=1;i<=n;i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } divide(1,n); cout<<"Vectorul sortat:"; for(i=1;i<=n;i++) cout<<a[i]<<" ";}

În programul principal se citesc numărul de elemente din vectorul a, se citesc elementele vectorului a şi se apelează funcţia divide(1,n) după care se afişează elementele vectorului sortat.