Q. Write a C program to that sort 5 numbers using merge sorting.
Ans.
/* c program for merge sorting */
#include<stdio.h>
#include<conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int );
int main()
{
int arr[30];
int i,size;
printf("\n\t------- Merge sorting method -------\n\n");
printf("Enter total no. of elements : ");
scanf("%d",&size);
for(i=0; i<size; i++)
{
printf("Enter %d element : ",i+1);
scanf("%d",&arr[i]);
}
part(arr,0,size-1);
printf("\n\t------- Merge sorted elements -------\n\n");
for(i=0; i<size; i++)
printf("%d ",arr[i]);
getch();
return 0;
}
void part(int arr[],int min,int max)
{
int mid;
if(min<max)
{
mid=(min+max)/2;
part(arr,min,mid);
part(arr,mid+1,max);
merge(arr,min,mid,max);
}
}
void merge(int arr[],int min,int mid,int max)
{
int tmp[30];
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(arr[j]<=arr[m])
{
tmp[i]=arr[j];
j++;
}
else
{
tmp[i]=arr[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
tmp[i]=arr[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
tmp[i]=arr[k];
i++;
}
}
for(k=min; k<=max; k++)
arr[k]=tmp[k];
}
/************* OUTPUT *****************/
Ans.
/* c program for merge sorting */
#include<stdio.h>
#include<conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int );
int main()
{
int arr[30];
int i,size;
printf("\n\t------- Merge sorting method -------\n\n");
printf("Enter total no. of elements : ");
scanf("%d",&size);
for(i=0; i<size; i++)
{
printf("Enter %d element : ",i+1);
scanf("%d",&arr[i]);
}
part(arr,0,size-1);
printf("\n\t------- Merge sorted elements -------\n\n");
for(i=0; i<size; i++)
printf("%d ",arr[i]);
getch();
return 0;
}
void part(int arr[],int min,int max)
{
int mid;
if(min<max)
{
mid=(min+max)/2;
part(arr,min,mid);
part(arr,mid+1,max);
merge(arr,min,mid,max);
}
}
void merge(int arr[],int min,int mid,int max)
{
int tmp[30];
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(arr[j]<=arr[m])
{
tmp[i]=arr[j];
j++;
}
else
{
tmp[i]=arr[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
tmp[i]=arr[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
tmp[i]=arr[k];
i++;
}
}
for(k=min; k<=max; k++)
arr[k]=tmp[k];
}
/************* OUTPUT *****************/
 |
| Screen shot for merge sort C program |
Related programs:
Thanks.Its very easy & simple to understand
ReplyDeleteeasy one...
ReplyDeleteThnx, its easy to understand
ReplyDeletewhat is the need of condition if(min<max) in part function??
ReplyDeleteit is the exit condition for the recursion
Deletewhat is the need of condition if(min<max) in part function??
ReplyDeletewhat about array part has size greater than 30 ?
ReplyDeleteYou must aware the size of array.
DeleteIf the size is increase the result will be wrong.
You can try DMA (Dynamic Memory Allocation) or always keep the big size or array.
you can also assign max as size of tmp[max] array because each time exactly required memory allocate to the tmp[] array.
DeleteThnx a lot :D
ReplyDeleteThanks its very useful
ReplyDeleteThank you so much!!!!!!
ReplyDeleteCan some one clarify what will be value of mid when its passed to merge function
ReplyDeletelets take a example you have a array arr[]={60,50,40,30,20,10};
Deletehere size(number of item)=6;
we will pass it as part(arr,0,size-1);
now,actually we are passing part(base address of array,lower value,upper value)
here,part(arr,0,5);
now in function part=>
void part(int arr[],int min,int max)
{
int mid;//initially default value
if(min<max)//0<5
{
mid=(min+max)/2;//now mid=((0+5)/2) which id 2.5 but due to int it will assign 2.
part(arr,min,mid);//part(arr,0,2)//as previous part() method work same for it as using recursion untill condition min<max condition fails....
part(arr,mid+1,max);//part(arr,2+1,5)//as previous part() method work same for it as using recursion untill condition min<max condition fails....
merge(arr,min,mid,max);//merge(arr,0,3,5)
}
}
why this code is returning address of sorted elements....
ReplyDelete#include
void mergesort(int[],int);
void merge(int[],int,int[],int,int[],int);
main()
{
int a[6]={3,5,2,7,5,1};
int n=6,i;
mergesort(a,n);
for(i=0;i<n;i++)
{
printf("\n%d",a[i]);
}
}
void merge(int left[],int mid,int right[],int n_mid,int a[],int n)
{
int i,j,k;
i=j=k=0;
while(i<mid&&j<n_mid)
{
if(left[i]<right[i])
{
a[k]=left[i];
i++;
}
else
{
a[k]=right[j];
j++;
}
k++;
}
while(i<mid)
{
a[k]=left[i];
i++;
k++;
}
while(j<n_mid)
{
a[k]=right[j];
j++;
k++;
}
}
void mergesort(int a[],int n)
{
int i;
if(n<2)
return;
int mid=n/2;
int n_mid=n-mid;
int left[mid],right[n_mid];
for(i=0;i<mid-1;i++)
{
left[i]=a[i];
}
for(i=mid;i<n-1;i++)
{
right[i-mid]=a[i];
}
mergesort(left,mid);
mergesort(right,n_mid);
merge(left,mid,right,n_mid,a,n);
}
#include
ReplyDeletevoid main()
{
int A[10],B[10],C[20];
int i, j,k;
int n1,n2,n3;
printf(" Enter the number of elements in A[] \n");
scanf("%d", &n1);
printf(" Enter the Array elements of A[] in sorted form \n");
for (i = 0; i < n1; i++)
scanf("%d", &A[i]);
printf(" A[] Entered is \n");
for (i = 0; i < n1; i++)
printf(" %d", A[i]);
printf("\n Enter the number of elements of B[] \n");
scanf("%d", &n2);
printf(" Enter the Array elements of B[] in sorted form\n");
for (i = 0; i < n2; i++)
scanf("%d", &B[i]);
printf(" B[] Entered is \n");
for (i = 0; i < n2; i++)
printf(" %d", B[i]);
i=0;j=0;
k=0;
while (i<n1 && j<n2)
{
if (A[i]<=B[j])
{
C[k]=A[i];
i++;
}
else
{
C[k]=B[j];
j++;
}
k++;
}
while (i<n1)
{
C[k]=A[i];
i++;
k++;
}
while (j<n2)
{
C[k]=B[j];
j++;
k++;
}
n3=n1+n2;
printf("\n New Array is...\n");
for (i = 0; i < n3; i++)
printf(" %d",C[i]);
}
its very useful for classes
ReplyDeleteCan u explain this 4 me
Deletethanks...very helpful.....
ReplyDeleteplease help to calculate time complexity of merge algorithm
ReplyDeleteThanks.......easily understandable
ReplyDeletevoid mergeSort(int *x, int start1, int end2) {
ReplyDeleteif (start1 >= end2)
return;
int i, j, k, end1 = (start1 + end2) / 2, start2 = end1 + 1, A[20], B[20], n1 = start2 - start1, n2 = end2 - end1;
mergeSort(x, start1, end1);
mergeSort(x, start2, end2);
for (i = 0; i < n1; i++)
A[i] = x[start1 + i];
for (i = 0; i < n2; i++)
B[i] = x[start2 + i];
i = j = k = 0;
while (i < n1 && j < n2)
if (A[i] < B[j])
x[start1 + k++] = A[i++];
else
x[start1 + k++] = B[j++];
if (i == n1)
while (j < n2)
x[start1 + k++] = B[j++];
else if (j == n2)
while (i < n1)
x[start1 + k++] = A[i++];
}
easy to understand
ReplyDelete#include
ReplyDeleteint merge(int *,int,int,int);
int merge_sort(int *,int,int);
int main()
{
int v[100000],n,i,ip,ir;
printf("Tamano del arreglo: \n");
scanf("%d",&n);
printf("Introduzca %d numeros: \n", n);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
merge_sort(v,0,n-1);
printf("Numeros ordenados: \n");
for(i=0;i<n;i++)
printf("%d \n",v[i]);
getch();
return 0;
}
int merge_sort(int *v,int ip,int ir)
{
int iq;
if(ip<ir)
{
iq=(ip+ir)/2;
merge_sort(v,ip,iq);
merge_sort(v,iq+1,ir);
merge(v,ip,iq,ir);
}
return 0;
}
int merge(int *v,int ip,int iq,int ir)
{
int n1,n2,i,j,k,L[500],R[500];
n1=iq-ip+1;
n2=ir-iq;
for(i=0;i<n1;i++)
L[i]=v[ip+i];
for(j=0;j<n2;j++)
R[j]=v[iq+j+1];
L[n1]=32765;
R[n2]=32765;
i=0;j=0;
for(k=ip;k<=ir;k++)
{
if(L[i]<=R[j])
{
v[k]=L[i];
i=i+1;
}
else
{
v[k]=R[j];
j=j+1;
}
}
return 0;
}
very lenghty program,but easier to understand
ReplyDelete