lot of people are finding difficulty in left[i]= 10000 so here's the solution
well in my previous blog yesterday the approach that i followed was similar to cormen where they initialize the the next element after filling the let and right sub array as ∞ which means the element should be higher than all the elements present for sorting but that may not be the case .. as you will never know what a person can enter .
here some people will say that we can enter the largest that is available for that language for example for c it signed 32467 ( for 32 bit compiler ) and it can also vary from system to system so you can use this approach
#include<stdio.h>
#include<conio.h>
void main()
{
int i,array1[]={1,5,7,84,32,76,41,62,79,13};
merge(array1,0,9);
for( i=0;i<=9;i++)
{
printf("%d\n",array1[i]);
}
}
void merge(int *A,int p,int n)
{
if (p==n)
{
return;
}
else
{
int q=p+(n-p)/2;
printf("now calling merge(A,%d,%d)\n",p,q);
merge(A,p,q);
printf(" now calling merge(A,%d,%d)\n",q+1,n);
merge(A,q+1,n);
printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
combine(A,p,q,n);
}
}
void combine(int *A,int p,int x,int n)
{
int i = 0;
int j=0;
int n1 = p ;
int n2 = x;
int left[10];
int right[10];
for( i=0;p<=x;i++,p++)
{
left[i] = A[p];
printf("the element added in left now which is %d",left[i]);
}
for(i=0;(x+1)<=n;x++,i++)
{
right[i] = A[x+1];
printf("the element added in right now which is %d",right[i]);
}
printf("\n");
p=n1; /*now p contains the starting value as we modified the value in first loop */
for(i=0,j=0;(i<n2-n1+1)&&(j<n-n2);p++) /* as (n2-n1+1) would be giving the number of elements in left array but here in left array we are starting from 0 that's why we didn't use equal to sign*/
{
if((i!=n2-n1+1)&&(left[i]<right[j]))
{
A[p]=left[i];
printf("the element added in A[%d] which is %d \n",n1,A[p]);
i++;
}
else
{
A[p]= right[j];
printf("the element added from right \n",A[p]);
j++;
}
}
if(i == n2-n1+1 ) /*means all the elements of the left array are copied but there can be elements in right */
{
for(;j<n2-n1;j++)
{
A[p]=right[j];
p++;
}
}
else /*means all the elements of the right array are copied but there can be elements in left */
{
for(;i<n2-n1+1;i++)
{
A[p]=left[i];
p++;
}
}
}
well in my previous blog yesterday the approach that i followed was similar to cormen where they initialize the the next element after filling the let and right sub array as ∞ which means the element should be higher than all the elements present for sorting but that may not be the case .. as you will never know what a person can enter .
here some people will say that we can enter the largest that is available for that language for example for c it signed 32467 ( for 32 bit compiler ) and it can also vary from system to system so you can use this approach
#include<stdio.h>
#include<conio.h>
void main()
{
int i,array1[]={1,5,7,84,32,76,41,62,79,13};
merge(array1,0,9);
for( i=0;i<=9;i++)
{
printf("%d\n",array1[i]);
}
}
void merge(int *A,int p,int n)
{
if (p==n)
{
return;
}
else
{
int q=p+(n-p)/2;
printf("now calling merge(A,%d,%d)\n",p,q);
merge(A,p,q);
printf(" now calling merge(A,%d,%d)\n",q+1,n);
merge(A,q+1,n);
printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
combine(A,p,q,n);
}
}
void combine(int *A,int p,int x,int n)
{
int i = 0;
int j=0;
int n1 = p ;
int n2 = x;
int left[10];
int right[10];
for( i=0;p<=x;i++,p++)
{
left[i] = A[p];
printf("the element added in left now which is %d",left[i]);
}
for(i=0;(x+1)<=n;x++,i++)
{
right[i] = A[x+1];
printf("the element added in right now which is %d",right[i]);
}
printf("\n");
p=n1; /*now p contains the starting value as we modified the value in first loop */
for(i=0,j=0;(i<n2-n1+1)&&(j<n-n2);p++) /* as (n2-n1+1) would be giving the number of elements in left array but here in left array we are starting from 0 that's why we didn't use equal to sign*/
{
if((i!=n2-n1+1)&&(left[i]<right[j]))
{
A[p]=left[i];
printf("the element added in A[%d] which is %d \n",n1,A[p]);
i++;
}
else
{
A[p]= right[j];
printf("the element added from right \n",A[p]);
j++;
}
}
if(i == n2-n1+1 ) /*means all the elements of the left array are copied but there can be elements in right */
{
for(;j<n2-n1;j++)
{
A[p]=right[j];
p++;
}
}
else /*means all the elements of the right array are copied but there can be elements in left */
{
for(;i<n2-n1+1;i++)
{
A[p]=left[i];
p++;
}
}
}
when i am combing the arrays the loop will come out if only the i or j index have reached boundry conditions and now in if else condition i am checking which index has achieved boundary conditions as if it j then i will simply copy all the elements of left array in A that is the final array or if it was i then i am copying all the remaining elements from left array .
Here i tried to keep the previous program as it is ..with minimal changes ... so that you can understand the idea .. well other approaches are also possible ..
as once a great mathematician said " there are infinitely many solutions possible for a single problem "
so try to program it and find newer approaches by yourself
No comments:
Post a Comment