soratrea

[•mihai.plesa]

Am facut acest program pentru sortarea prin interclasare:

Cod:

#include <cstdio>
using namespace std;
int main()
{FILE*f=fopen("fis.in","r");
FILE*g=fopen("fis.out","w");
int a[100],b[100],c[100],i,j,k,n,m,l;
fscanf(f,"%d %d",&n,&m);
for(i=1; i<=n; i++)
	fscanf(f,"%d",&a[i]);

for(j=1; j<=m; j++)
	fscanf(f,"%d",&b[i]);
i=1;
j=1;
k=1;
while(i<=n && j<=m){
	if(a[i]<=b[j]) {c[k]=a[i]; i=i+1;}
	if(a[i]>=b[j]) {c[k]=b[j]; j=j+1;}
	k=k+1;
}
if(i<n)
	for(l=i; l<=n; l++){
		k=k+1;
		c[k]=a[l];
	}
if(j<m)
	for(l=1; l<=m-j; l++){
		k=k+1;
		c[k]=b[l];
	}
for(i=1; i<=k; i++)
	fprintf(g,"%d ",c[i]);
}

Unde gresesc?
Multumesc!
Foloseste tag-ul [ code ] ... [ / code ] cand postezi o sursa

[•blasterz]

Tu faci doar interclasarea a 2 siruri sortate, nu sortarea propriuzisa.
Daca sirurile a si b sunt sortate (iar sursa e implementata bine) ar trebui sa obtii un sir sortat.

Ideea e sa folosesti divide et impera:

Cod:

void sort(int a[], int left, int right)
{
     if (left == right) // un singur element este sortat
        return;
     // apelez recursiv pt prima respectiv a 2a jumatate a sirului
     sort (a, left, (left + right) / 2);
     sort (a, (left + right) / 2 + 1, right);
    // acum cele 2 jumatati sunt sortate, deci le pot interclasa si obtin un sir sortat
    interclasare (a, left, right);

}