Advertisement
shabbyheart

Untitled

Nov 3rd, 2019
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int cont = 0,c = 0;
  4. void marge(int arr[],int beg,int mid,int end)
  5. {
  6.     int l = mid - beg+1, r = end - mid;
  7.     int left[l],right[r];
  8.     for( int  i = 0 ; i< l; i++)
  9.     {
  10.         left[i] = arr[beg+i];
  11.     }
  12.     for( int  i = 0 ; i< l; i++)
  13.     {
  14.         right[i] = arr[mid+1+i];
  15.     }
  16.  
  17.     int i = 0,j = 0,k=beg;
  18.  
  19.     while( i< l && j < r)
  20.     {
  21.         if( left[i] <= right[j])
  22.         {
  23.            arr[k] = right[j];
  24.            //i++;
  25.            j++;
  26.         }
  27.         else
  28.         {
  29.             cont++;
  30.             arr[k] = left[i];
  31.             cout<<left[i] <<" "<<right[j]<<endl;
  32.             //j++;
  33.             i++;
  34.         }
  35.         k++;
  36.     }
  37.       while(i< l)
  38.     {
  39.         arr[k] = left[i];
  40.         i++;
  41.         k++;
  42.     }
  43.     while( j < r )
  44.     {
  45.         arr[k] = right[j];
  46.         j++;
  47.         k++;
  48.     }
  49.  
  50. }
  51.  
  52. void margeSort(int arr[],int beg,int end)
  53. {
  54.     if(beg < end)
  55.     {
  56.         int mid = (beg+end) / 2;
  57.         margeSort(arr,beg,mid);
  58.         margeSort(arr,mid+1,end);
  59.         marge(arr,beg,mid,end);
  60.  
  61.     }
  62. }
  63. void display(int arr[])
  64. {
  65.     for( int i = 0; i<5; i++)
  66.     {
  67.         cout<<arr[i]<< " ";
  68.     }
  69. }
  70. int main()
  71. {
  72.     freopen("input.txt","r",stdin);
  73.     int arr[1000],left[1000],right[1000];
  74.     for(int i = 0; i < 6; i++)
  75.     {
  76.         cin>>arr[i];
  77.     }
  78. //    for(int i = 0; i < 5; i++)
  79. //    {
  80. //        cout<<arr[i];
  81. //    }
  82.  
  83. //    for(int i = 0; i < 5; i++)
  84. //    {
  85. //        marge(arr,left,right,l,r);
  86. //    }
  87.     margeSort(arr,0,5);
  88.     //display(arr);
  89.     cout<<endl;
  90.     cout<<cont;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement