Suppose there are two arrays int a [10] and int b [10].The operation that combines this two arrays is called merging. If the arrays are not in sorted order then we may first sort them and after that may be merged. It is also possible to merge them first and after that the sorting will be done.
Algorithm for sorting the two arrays first and then merging them:-
A and B are two arrays with n and m number of elements. Both the arrays are in sorted order. C is the final array where the final values will be stored. I, J and K are three integer type variables with initial value 0 .They will be used as array index or the three arrays.
Repeat the following steps while ((I< n) and (J< m))
If A [I] < B [J]
C [K] =A [I]
I=I+1
K=K+1
Else if A [I] >B [J]
C [K] =B [J]
J=J+1
K=K+1
Else [This situation means both are same, so any one of the values can be set in the final array]
C [K] =A [I]
I=I+1
J=J+1
K=K+1
[End of loop]
If I< n [means first array has more values]
Repeat the following steps for I=I, I+1…n-1
C [K] =A [I]
I=I+1
K=K+1
[End of loop]
Else If (J, m)
Repeat the following steps for J=J, J+1…m-1
C [K] =B [J]
J=J+1
K=K+1
[End of loop]
End
Program on merge sort:-
# include< stdio.h>
bsort(int n, int l[])
{
int flag = 1 ;
int i, j, k, temp;
for(j = 0 ; j< n - 1; j++)
{
for(k = 0 ; k< n - j - 1 ; k++)
{
if(l[k] > l[k+1])
{
temp = l[k];
l[k] = l[k+1];
l[k+1] = temp ;
flag = 0;
}
}
if(flag)
break ;
else
flag = 1;
}
printf("\n Entered list as follows in");
printf("\n Ascending order: ");
for(i = 0 ; i < n ; i++)
printf(" %d", l[i]);
}
msort( int n, int list_a[], int m ,int list_b[], int result_list[] )
{
int i = 0;
int j = 0;
int k = 0;
int ch, l;
while((i < n) &&(j< m))
{
if(list_a[i] < list_b[j])
{
result_list[k] = list_a[i];
i++;
k++;
}
else if(list_a[i] > list_b[j])
{
result_list[k] = list_b[j];
j++;
k++;
}
else
{
result_list[k] = list_a[i];
i++;
j++;
k++;
}
printf("\n");
for(ch = 0; ch < k; ch++)
printf(" %d", result_list[ch]);
}
if(i < n )
{
for(l = i ; l < n ; l++)
{
result_list[k] = list_a[i];
i++;
k++;
printf("\n");
for(ch = 0; ch < k; ch++)
printf(" %d", result_list[ch]);
}
}
else if(j < m)
{
for(l = j; l< m; l++)
{
result_list[k] = list_b[j];
j++;
k++;
printf("\n");
for(ch = 0; ch < k; ch++)
printf(" %d", result_list[ch]);
}
}
return k;
}
void main()
{
int list_a[100],list_b[100];
int result[200];
int n, m, k, i;
clrscr();
printf("\n Input the number of elements of list_a: ");
scanf("%d", &n);
for(i = 0; i< n ; i++)
{
printf("\n Input the element: %d: ", i+1);
scanf("%d", &list_a[i]);
}
bsort(n, list_a);
printf("\n Input the number of elements of list_b:");
scanf("%d", &m);
for(i = 0 ; i< m ; i++)
{
printf("\n Input the element: %d: ", i+1);
scanf("%d", &list_b[i]);
}
bsort(m, list_b);
k = msort( n, list_a, m , list_b, result);
printf("\n Sorted list is as follows:\n");
for(i = 0 ; i< k ; i++)
{
printf(" %d", result[i]);
}
getch();
}
No comments:
Post a Comment