-
-
Save mbalayil/898596 to your computer and use it in GitHub Desktop.
/** | |
* Divide : Divide the n-element array into two n/2-element | |
* sub-arrays | |
* Conquer : Sort the two sub-arrays recursively using | |
* merge sort | |
* Combine : Merge the two sorted subsequences to form the | |
* sorted array | |
**/ | |
#include<stdio.h> | |
int arr[20]; // array to be sorted | |
int main() | |
{ | |
int n,i; | |
printf("Enter the size of array\n"); // input the elements | |
scanf("%d",&n); | |
printf("Enter the elements:"); | |
for(i=0; i<n; i++) | |
scanf("%d",&arr[i]); | |
merge_sort(arr,0,n-1); // sort the array | |
printf("Sorted array:"); // print sorted array | |
for(i=0; i<n; i++) | |
printf("%d",arr[i]); | |
return 0; | |
} | |
int merge_sort(int arr[],int low,int high) | |
{ | |
int mid; | |
if(low<high) { | |
mid=(low+high)/2; | |
// Divide and Conquer | |
merge_sort(arr,low,mid); | |
merge_sort(arr,mid+1,high); | |
// Combine | |
merge(arr,low,mid,high); | |
} | |
return 0; | |
} | |
int merge(int arr[],int l,int m,int h) | |
{ | |
int arr1[10],arr2[10]; // Two temporary arrays to | |
hold the two arrays to be merged | |
int n1,n2,i,j,k; | |
n1=m-l+1; | |
n2=h-m; | |
for(i=0; i<n1; i++) | |
arr1[i]=arr[l+i]; | |
for(j=0; j<n2; j++) | |
arr2[j]=arr[m+j+1]; | |
arr1[i]=9999; // To mark the end of each temporary array | |
arr2[j]=9999; | |
i=0; | |
j=0; | |
for(k=l; k<=h; k++) { //process of combining two sorted arrays | |
if(arr1[i]<=arr2[j]) | |
arr[k]=arr1[i++]; | |
else | |
arr[k]=arr2[j++]; | |
} | |
return 0; | |
} |
I'm getting a runtime error for thiscode
include<stdio.h>
void merge_sort(int [],int ,int );
void merge(int [], int ,int ,int );
int main()
{
int n,A[n+1],p,r,i;
printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter the elements to be sorted\n");
for(i=0;i<n;i++)
{
scanf("%d",&A[i]);
}
p=0;
r=n-1;
merge_sort(A,p,r);
printf("the sorted list is\n");
for(i=0;i<n;i++)
{
printf("%d\t",A[i]);
}
return 0;
}
void merge_sort(int A[],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q+1,r);
merge(A,p,q,r);
}
}
void merge(int A[],int p, int q , int r)
{
int n1,n2,L[n1],R[n2],i,j,k;
n1=q-p+1;
n2=r-q;
for(i=0;i<n1;i++)
{
L[i]=A[p+i];
}
L[i]=9999999;
for(j=0;j<n2;j++)
{
R[j]=A[q+j+1];
}
R[j]=9999999;
i=0;
j=0;
for(k=p;k<=r;k++)
{
if(L[i]<=R[i])
{
A[k]=L[i++];
}
else
{
A[k]=R[j++];
}
}
}
#include<stdio.h>
int arr[20]; // array to be sorted
int merge(int arr[],int l,int m,int h)
{
int arr1[10],arr2[10]; // Two temporary arrays to hold the two arrays to be merged
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0; i<n1; i++)
arr1[i]=arr[l+i];
for(j=0; j<n2; j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
return 0;
}
int main()
{
int n,i;
printf("Enter the size of array\n"); // input the elements
scanf("%d",&n);
printf("Enter the elements:");
for(i=0; i<n; i++)
scanf("%d",&arr[i]);
merge_sort(arr,0,n-1); // sort the array
printf("Sorted array:"); // print sorted array
for(i=0; i<n; i++)
printf("%d ",arr[i]);
return 0;
}
`
Hey can someone explain me what's happening at these 2 lines?
merge_sort(arr,low,mid); /This line calling function int merge_sort(int arr[],int low,int high) again? And passing value of high as same as new value of mid?/
merge_sort(arr,mid+1,high);/* Similarly,here this line calling function int merge_sort(int arr[],int low,int high) again? And passing value of low same as mid +1 ? */
What is the right explanation?
can you change this code to descending version?
Helped me a lot. Thanks.
- implement insertion sort,
- generated 1 M random input
- write the input in a file
if possible solve this problem
I tried this code in codeblocks and ideone but it seems that time taken for sorting 35 elements is 1.98 seconds and beyond that the code shows terminated due to time out in ideone.