Shishu

marge sort in c

Oct 19th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.44 KB | None | 0 0
  1. #include <stdio.h>
  2. #include<time.h>
  3. #define N 25
  4.  
  5.  
  6. int Arr[N+1];
  7.  
  8.  
  9. int Merge(int A[],int p,int q,int r)
  10. {
  11.     int n1 = q-p+1;
  12.     int n2 = r-q;
  13.     int L[n1];
  14.     int R[n2];
  15.     int i,j,k;
  16.  
  17.     for(i=0; i<n1; i++)
  18.         L[i] = A[p+i];
  19.     for(i=0; i<n2; i++)
  20.         R[i] = A[q+i+1];
  21.  
  22.     L[n1] = 15000;
  23.     R[n2] = 15000;
  24.  
  25.     i=0;
  26.     j=0;
  27.  
  28.     for(k=p; k<=r; k++)
  29.     {
  30.         if(L[i]<=R[j])
  31.         {
  32.             A[k] = L[i];
  33.             i = i+1;
  34.         }
  35.         else
  36.         {
  37.             A[k] = R[j];
  38.             j = j+1;
  39.         }
  40.     }
  41.  
  42. }
  43.  
  44. int MergeSort(int A[],int p,int r)
  45. {
  46.  
  47.     int x, y, z;
  48.     if(p<r)
  49.     {
  50.         int q = (p+r)/2;
  51.         //Explanation of "divide" part
  52.  
  53.         for(x=p; x<=q; x++)
  54.         {
  55.             printf("%d ", A[x]);
  56.         }
  57.         printf("\t\t");
  58.         for(x=q+1; x<=r; x++)
  59.         {
  60.             printf("%d ", A[x]);
  61.         }
  62.         printf("\n\n");
  63.  
  64.  
  65.         MergeSort(A,p,q);
  66.         MergeSort(A,q+1,r);
  67.         printf("\n");
  68.         Merge(A,p,q,r);
  69.     }
  70.     else
  71.         return 0;
  72. }
  73.  
  74. int main()
  75. {
  76.     int i;
  77.     srand(time(NULL));
  78.     for(i=0; i<N; i++)
  79.     {
  80.         Arr[i] = rand()%100+1;
  81.         printf("%d ",Arr[i]);
  82.     }
  83.     printf("\n");
  84.     printf("\n\t\tDIVIDE\n");
  85.     MergeSort(Arr,0,N-1);
  86.     printf("\n------------------SORTED ARRAY---------------------\n");
  87.     for(i=0; i<N; i++)
  88.         printf("%d ",Arr[i]);
  89. }
Add Comment
Please, Sign In to add comment