Tuesday, November 9, 2010

Marge sort algorithgm c implementation

#include
#include
#include

int *a;

merge(int p,int q,int r)
{
  int n1,n2,i,j,k;
  int *L,*R;
  n1=q-p+1;
  n2=r-q;
  L=(int*)malloc(sizeof(int)*(n1+2));
  R=(int*)malloc(sizeof(int)*(n2+2));
  for(i=1;i<=n1;i++)
  L[i]=a[p+i-1];
  for(j=1;j<=n2;j++)
  R[j]=a[q+j];
  L[n1+1]=-1;
  R[n2+1]=-1;
  i=1;
  j=1;
  for(k=p;k<=r;k++)
  {
  if(L[i]<=R[j]&&L[i]!=-1)
  {
   a[k]=L[i];
   i++;
  }
  else
  {
   if(R[j]!=-1)
   {
    a[k]=R[j];
    j++;
   }
   else
   {
    while(L[i]!=-1)
    {
     a[k]=L[i];
     i++;
     k++;

    }
   }
  }

  }
  free(L);
  free(R);
}

merge_sort(int p,int r)
{
  int q;
  if(p
  {
  q=(p+r)/2;
  if((p+r)%2==0)
   q=q-1;
  merge_sort(p,q);
  merge_sort(q+1,r);
  merge(p,q,r);
  }
}

void main()
{
 clrscr();
 int i,j,k,p,r;
 printf("How many numbers : ");
 scanf("%d",&i);
 a=(int*)malloc(sizeof(int)*(i+1));
 printf("\nEnter the numbers : ");
 for(k=1;k<=i;k++)
 {
  scanf("%d",&j);
  a[k]=j;
 }
 p=1;
 r=i;
 merge_sort(p,r);
 printf("\nSorted list is :   ");

 for(k=1;k<=i;k++)
  printf("   %d",a[k]);

 free(a);
 getch();
}

No comments:

Post a Comment