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

25 comments:

  1. Thanks.Its very easy & simple to understand

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

    ReplyDelete
    Replies
    1. it is the exit condition for the recursion

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

    ReplyDelete
  4. what about array part has size greater than 30 ?

    ReplyDelete
    Replies
    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.

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

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

    ReplyDelete
    Replies
    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)
      }
      }

      Delete
  6. 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);
    }

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

    ReplyDelete
  8. please help to calculate time complexity of merge algorithm

    ReplyDelete
  9. Thanks.......easily understandable

    ReplyDelete
  10. 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++];
    }

    ReplyDelete
  11. #include
    int merge(int *,int,int,int);
    int merge_sort(int *,int,int);
    int main()
    {
    int v[100000],n,i,ip,ir;

    printf("Tamano del arreglo: \n");
    scanf("%d",&n);
    printf("Introduzca %d numeros: \n", n);
    for(i=0;i<n;i++)
    scanf("%d",&v[i]);
    merge_sort(v,0,n-1);
    printf("Numeros ordenados: \n");
    for(i=0;i<n;i++)
    printf("%d \n",v[i]);
    getch();
    return 0;
    }
    int merge_sort(int *v,int ip,int ir)
    {
    int iq;
    if(ip<ir)
    {
    iq=(ip+ir)/2;
    merge_sort(v,ip,iq);
    merge_sort(v,iq+1,ir);
    merge(v,ip,iq,ir);
    }
    return 0;
    }
    int merge(int *v,int ip,int iq,int ir)
    {
    int n1,n2,i,j,k,L[500],R[500];
    n1=iq-ip+1;
    n2=ir-iq;
    for(i=0;i<n1;i++)
    L[i]=v[ip+i];
    for(j=0;j<n2;j++)
    R[j]=v[iq+j+1];
    L[n1]=32765;
    R[n2]=32765;
    i=0;j=0;
    for(k=ip;k<=ir;k++)
    {
    if(L[i]<=R[j])
    {
    v[k]=L[i];
    i=i+1;
    }
    else
    {
    v[k]=R[j];
    j=j+1;
    }
    }
    return 0;
    }

    ReplyDelete
  12. very lenghty program,but easier to understand

    ReplyDelete