Advertisement
Md_hosen_zisad

merge with insertion

Oct 22nd, 2018
405
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int arr[100];
  5.  
  6.  
  7. void insertionSort(int arr[], int n  ){
  8.         int i , j ,key ;
  9.         for(i=1 ;i<n ; i++){
  10.            key=arr[i] ;
  11.            j= i-1 ;
  12.  
  13.            while (j >= 0 && arr[j] > key)
  14.        {
  15.            arr[j+1] = arr[j];
  16.            j = j-1;
  17.        }
  18.        arr[j+1] = key;
  19.    }
  20. }
  21.  
  22.  
  23.  
  24.  
  25. void merge(int arr[], int l, int m, int r)
  26. {
  27.     int i, j, k;
  28.     int n1 = m - l + 1;
  29.     int n2 =  r - m;
  30.  
  31.     int L[n1], R[n2];
  32.  
  33.     for (i = 0; i < n1; i++)
  34.         L[i] = arr[l + i];
  35.     for (j = 0; j < n2; j++)
  36.         R[j] = arr[m + 1+ j];
  37.  
  38.     i = 0;
  39.     j = 0;
  40.     k = l;
  41.     while (i < n1 && j < n2)
  42.     {
  43.         if (L[i] <= R[j])
  44.         {
  45.             arr[k] = L[i];
  46.             i++;
  47.         }
  48.         else
  49.         {
  50.             arr[k] = R[j];
  51.             j++;
  52.         }
  53.         k++;
  54.     }
  55.  
  56.  
  57.     while (i < n1)
  58.     {
  59.         arr[k] = L[i];
  60.         i++;
  61.         k++;
  62.     }
  63.  
  64.  
  65.     while (j < n2)
  66.     {
  67.         arr[k] = R[j];
  68.         j++;
  69.         k++;
  70.     }
  71. }
  72.  
  73. void mergeSort(int arr[], int l, int r)
  74. {
  75.     if (l < r)
  76.     {
  77.  
  78.         int m = l+(r-l)/2;
  79.  
  80.         mergeSort(arr, l, m);
  81.         mergeSort(arr, m+1, r);
  82.  
  83.         merge(arr, l, m, r);
  84.     }
  85. }
  86.  
  87.  
  88.  
  89. int main()
  90. {
  91.  
  92.  
  93.      int i , n;
  94.     cout<<"Enter number :";
  95.     cin>>n;
  96.     for(i=0 ; i<n ; i++){
  97.         cin>>arr[i];
  98.     }
  99.  
  100.         if(n<16)
  101.             insertionSort(arr,n);
  102.         else
  103.         mergeSort(arr,0,n-1);
  104.  
  105.     cout<<"Sorted array is :";
  106.     //printArray(arr, n);
  107.      for(i=0 ; i<n ; i++){
  108.         cout<<arr[i]<<" ";
  109.     }
  110.     return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement