MergeSort (Sortare prin interclasare)
Acest model de sortare urmeaza indeaproape pasii metodei Divide et Impera.
Intuitiv, aceasta urmeaza pasii:
Imparte: Descompune sirul de n elemente care urmeaza a fi ordonat in 2 cate 2 subsiruri de cate n/2 elemente.
Stapaneste: Ordoneaza recursiv cele 2 subsiruri folosind interclasarea.
Combina: Interclaseaza cele 2 siruri ordonate. Acest pas este repezentat de procedura merge si interclaseaza cei 2 vectori: primul cu elementele de pe pozitiile p...m, al doilea cu elementele de pe pozitiile m+1...u pentru a forma vectorul sortat care va fi apoi copiat in vectorul initial.
Observatie: Recursivitatea se opreste cand sirul de sortat are un singur element, deoarece un sir cu un singur element este deja ordonat (aceasta este subproblema de dimensiune mica care se poate rezolva direct).
Functia merge_sort sorteaza elementele de pe pozitiile p...u din vectorul dat. Daca p>=u atunci subvectorul are un singur element si este deja sortat. Prin urmare ramura altfel (else) nu mai apare.
#include <iostream.h>
int a[50];
void merge(int,int,int);
void merge_sort(int p,int u)
{
int m;
if(p<u)
{
m=(p+u)/2;
merge_sort(p,m);
merge_sort(m+1,u);
merge(p,m,u);
}
}
void merge(int p,int m,int u)
{
int h,i,j,b[50],k;
/*b- vectorul in care se construieste vectorul ordonat prin interclasarea celor 2 subvectori*/
h=p;
i=p;
j=m+1;
/*introducem in b elementele din cei 2 subvectori in ordine crescatoare*/
while((h<=m)&&(j<=u))
{
if(a[h]<=a[j]) /*daca elementul curent din primul subvector este mai mare decat elementul curent din cel de-al doilea subvector, se va introduce in vectorul intermediar cel din cel de-al doilea subvector, altfel se va introduce cel din primul subvector*/
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
/*introducem in b elementele ramase in subvectorul din care nu s-au copiat toate elementele*/
if(h>m)
{
for(k=j;k<=u;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=m;k++)
{
b[i]=a[k];
i++;
}
}
/*copiem elementele vectorului intermediar in vectorul initial - cel care va avea elementele sortate*/
for(k=p;k<=u;k++) a[k]=b[k];
}
void main()
{
int n,i;
cout<<endl<<endl;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]=";cin>>a[i] ;
}
merge_sort(1,n);
cout<<endl;
cout<<"Sirul sortat"<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
}
