2.20.2012

Merge sorting

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 *****************/
 Screen shot for merge sort C program

Related programs:

1. Thanks.Its very easy & simple to understand

2. Thnx, its easy to understand

3. what is the need of condition if(min<max) in part function??

1. it is the exit condition for the recursion

4. what is the need of condition if(min<max) in part function??

5. what about array part has size greater than 30 ?

1. You must aware the size of array.
If the size is increase the result will be wrong.
You can try DMA (Dynamic Memory Allocation) or always keep the big size or array.

2. you can also assign max as size of tmp[max] array because each time exactly required memory allocate to the tmp[] array.

6. Thnx a lot :D

7. Thanks its very useful

8. Thank you so much!!!!!!

9. Can some one clarify what will be value of mid when its passed to merge function

1. lets take a example you have a array arr[]={60,50,40,30,20,10};
here 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)
}
}

10. why this code is returning address of sorted elements....

#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);
}

11. #include
void 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]);
}

12. its very useful for classes

1. Can u explain this 4 me

15. Thanks.......easily understandable

16. void mergeSort(int *x, int start1, int end2) {
if (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++];
}

17. easy to understand