Sunday 16 August 2015

program explaining merge sort without saving the random number in left and right array

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++;
        }
    }
}
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