My code here gets terminated after printing the unsorted array and also gives runtime error on ideone , i am unable to find the error in it . code works fine until the first mergesort in function but gets terminated afterwards without executing merge function . I have tried changing array size but nothing has worked so far . Any help would be appreciated.
#include<stdio.h>
#include<math.h>
void Merge(int arr[],int,int,int,int);
void printArray(int *arr,int n)
{
for (int i = 0; i < n; i )
{
printf("%d",arr[i]);
printf(" ");
}
printf("\n");
}
void MergeSort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid = ceil((low high)/2);
MergeSort(arr,low,mid-1);
MergeSort(arr,mid,high);
Merge(arr,low,mid-1,mid,high);
}
}
void Merge(int arr[],int low,int mid1,int mid2, int high)
{
int i,c,j;
c = low;
i = low;
j = mid2;
int Temp[high-low 1];
while(i <= mid1 && j<= high)
{
if(arr[i]<arr[j])
{
Temp[c] = arr[i];
i ;
c ;
}
else
{
Temp[c] = arr[j];
j ;
c ;
}
}
while(i<=mid1)
{
Temp[c] = arr[i];
i ;
c ;
}
while(j<=high)
{
Temp[c] = arr[j];
j ;
c ;
}
for(int k=0;k<=high;k )
{
arr[k] = Temp[k];
}
}
int main(void)
{
int arr[] = {3,5,2,13,12,3,2,13,45};
int n = sizeof(arr)/sizeof(arr[0]);
printf("unsorted array: \n");
printArray(arr,n);
MergeSort(arr,0,n-1);
printf("sorted array: \n");
printArray(arr,n);
return 0;
}
CodePudding user response:
There are several issues:
ceil
is not useful as/
will perform an integer division and so has already rounded down- Related to this, you should not use
mid-1
andmid
as arguments in the next recursive calls, butmid
andmid 1
. The same should be done with the arguments toMerge
. - The way you access
Temp
is wrong. You allocate entries from 0 tohigh-low
, but start your access with a value ofc
that islow
. You should instead start at index 0. - In the very last loop
k
runs from 0 tohigh
, but that are too many iterations. It should start fromlow
, and then the index access toTemp
should again be adapted by usingk-low
as index.
Here is the corrected code:
void MergeSort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid = (low high)/2; // <--
MergeSort(arr,low,mid); // <--
MergeSort(arr,mid 1,high); // <--
Merge(arr,low,mid,mid 1,high); // <--
}
}
void Merge(int arr[],int low,int mid1,int mid2, int high)
{
int i,c,j;
c = 0; // <--
i = low;
j = mid2;
int Temp[high-low 1];
while(i <= mid1 && j<= high)
{
if(arr[i]<arr[j])
{
Temp[c] = arr[i];
i ;
c ;
}
else
{
Temp[c] = arr[j];
j ;
c ;
}
}
while(i<=mid1)
{
Temp[c] = arr[i];
i ;
c ;
}
while(j<=high)
{
Temp[c] = arr[j];
j ;
c ;
}
for(int k=low;k<=high;k ) // <--
{
arr[k] = Temp[k-low]; // <--
}
}
Important note: I debugged the code for you, but this is something you can do yourself. Inspect the variables as you step through the code with a debugger, and spot where things are unexpected. It takes some time, but it is a skill a coder needs to learn.