interclasare divide et impera

Sortarea prin interclasare (merge-sort)

mergesort

Utilizand metoda divide et impera, sa se sorteze prin interclasare un sir

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

void mergesort(int i,int m,int j)

{int b[20],x=i,k=1,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);
mergesort(i,m,j);}
}

void main()
{
cout<<“n=”;
cin>>n;
for(int i=1;i<=n;i++)
{cout<<“a[“<<i<<“]=”;
cin>>a[i];
}
divimp(1,n);
cout<<“vectorul sortat este: “<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<‘ ‘;
}

Facebook Comments