Scribd
Încărcați
193 vizualizări4 pagini

Sortarea Prin Interclasare

Algoritmul de sortare prin interclasare (MergeSort) împarte vectorul în subvectori mai mici până când rămân doar elemente unice, apoi le interclasează înapoi într-un vector sortat.

Încărcat de

Deneanu
Drepturi de autor
© © All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd
193 vizualizări4 pagini

Sortarea Prin Interclasare

Algoritmul de sortare prin interclasare (MergeSort) împarte vectorul în subvectori mai mici până când rămân doar elemente unice, apoi le interclasează înapoi într-un vector sortat.

Încărcat de

Deneanu
Drepturi de autor
© © All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd

Sortarea prin interclasare(MergeSort)

Algoritmul de sortare prin interclasare se bazeaza pe observatia ca orice vector care


contine un singur element este un vector sortat. Algoritmul de interclasare se poate
folosi pentru sortarea unui vector cu ajutorul metodei divide et impera, astfel:
P1. se descompune problema in 2 subprobleme similare, prin impartirea vectorului
in doi subvectori, avand multimea indicilor [s,m] si [m+1,d], unde m este indicele
din mijlocul intervalului: m=(s+d)/2.
P2. Daca subvectorul contine un singur element, atunci se considera sortat; altfel,
se continua descompunerea lui in subvectorii care au multimea indicilor [p,m] si
[m+1,u].
P3. Se combina solutiile celor doua subprobleme, prin interclasarea celor 2 vectori
sortati, obtinandu-se un vector sortat.

10 8 7 9 5
10 8 7
10 8

95
7

8 10
7 8 10
5 7 8 9 10

5 9

#include <iostream>
using namespace std;
int n,a[100],c[100];
void citeste(int a[], int &n){
cout<<"n=";
cin>>n;
cout<<"dati elementele vectorului:";
for(int i=1;i<=n;i++)
{
cout<<"a["<<i<<"]=";
cin>>a[i];
}
}
void afiseaza(int c[],int n)
{
for(int i=1;i<=n;i++)
cout<<"a["<<i<<"]="<<c[i]<<endl;
}
void Interclaseaza(int p, int u, int m)
{
int i=p, j=m+1, k=1;
while(i<=m && j<=u) //i de la p la m si j de la m+1 la u
{
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++];

}
while(i<=m)
c[k++]=a[i++];
while(j<=u)
c[k++]=a[j++];
k=1;
i=p;
while(i<=u)
a[i++]=c[k++];
}
void divizeaza(int p, int u, int &m)
{
m=(p+u)/2;
}
void MergeSort(int a[],int p, int u) //sortare interclasare
{
int m;
if(p<u)
{
divizeaza(p,u,m);
MergeSort(a,p,m);
MergeSort(a,m+1,u);
Interclaseaza(p,u,m);
}
}
int main()
{

citeste(a,n);
MergeSort(a,1,n);
afiseaza(a,n);
return 0;
}

S-ar putea să vă placă și