Опитвах се да анализирам mergesort, но ме порази странен бъг. това е моят код:
int merge(int *a,int st,int mid,int en)
{
int i,j,l,m;
i = st;
l = st;
m = mid + 1;
while((l<=mid) && (m <= en))
{
if(a[l] <= a[m])
{
temp[i] = a[l];
l++;
i++;
}
else
{
temp[i] = a[m];
m++;
i++;
}
}
if(l <= mid)
{
for(j=l;j<=mid;j++)
{
temp[i] = a[j];
i++;
}
}
else
{
for(j=m;j<=en;j++)
{
temp[i] = a[j];
i++;
}
}
for(j=st;j<=en;j++) // ??
a[j] = temp[j]; // ??
}
void mergesort(int *a,int st,int en)
{
int mid;
if(st<en)
{
mid = (st+en)/2;
mergesort(a,st,mid);
mergesort(a,mid+1,en);
merge(a,st,mid,en);
}
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d\n",temp[i]);
getch();
return 0;
}
Използвам типичен код за сортиране чрез сливане. Изправен съм пред проблем да разбера защо е необходимо да копирам съдържанието от временния масив в основния масив, за да получа правилния изход. Опитах това на следния вход: 5 (брой термини) ,
4 4 5 3 2
И получавам изход като: 3 2 4 4 5 без да копирам съдържанието от временния масив в основния масив и ако направя копирането с помощта на цикъла „коментиран“, изходът е наред, т.е. 2 3 4 4 5. Аз съм просто не получавам, защо се случва това?
