SHARE
TWEET

Exercise OOP

sonprao Sep 24th, 2019 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(i=a;i<=b;i++)
  4. #define FOD(i,a,b) for(i=a;i>=b;i--)
  5. int n;
  6. bool Greater(int a, int b)
  7. {
  8.     return (a>b);
  9. }
  10. bool Lesser(int a, int b)
  11. {
  12.     return (a<b);
  13. }
  14. void input(int *a, int n)
  15. {
  16.     int i;
  17.     for(i=0;i<=n-1;i++)
  18.     cin>>*(a+i);
  19.     return;
  20. }
  21. void output(int *a, int n)
  22. {
  23.     int i;
  24.     for(i=0;i<=n-1;i++) cout<<*(a+i)<<" ";
  25.     cout<<endl;
  26.     return;
  27. }
  28. void insert(int *a, int *n, int k, int val)
  29. {
  30.     int i;
  31.     for(i=*n;i>=k-1;i--)
  32.         *(a+i+1)=*(a+i);
  33.     *(a+k-1)=val;
  34.     (*n)++;
  35.     return;
  36. }
  37. void del(int *a, int *n, int k)
  38. {
  39.     int i;
  40.     for(i=k-1;i<=(*n)-2;i++)
  41.     *(a+i)=*(a+i+1);
  42.     delete(*(a+*n-1));
  43.     (*n)--;
  44.     return;
  45. }
  46. void SWAP(int *a, int *b)
  47. {  
  48.     int x=*a;
  49.     *a=*b;
  50.     *b=x;
  51. }
  52. void  BubbleSort(int *a, int n, bool (*cmp)(int,int))
  53. {
  54.     int i,j;
  55.     for(i=0;i<=n-2;i++)
  56.     for(j=n-1;j>=i+1;j--)
  57.     if(cmp(*(a+j),*(a+i)))
  58.     {
  59.             SWAP(a+i,a+j);
  60.     }
  61.     return;
  62. }
  63. void SelectionSort(int *a,int n, bool (*cmp)(int,int))
  64. {
  65.     int i,j;
  66.     for(i=0;i<=n-2;i++)
  67.     for(j=i+1;j<=n-1;j++)
  68.     if (cmp(*(a+j),*(a+i)))
  69.         {
  70.             SWAP(a+i,a+j);
  71.         }
  72.     return;
  73. }
  74. void InsertionSort(int *a,int n,bool (*cmp)(int,int))
  75. {
  76.     int i,j;
  77.     for(i=1;i<=n-1;i++)
  78.     for(j=i;j>=1;j--)
  79.     if (cmp(*(a+j),*(a+j-1)))
  80.     {
  81.         SWAP(a+j,a+j-1);
  82.     }
  83.     return;
  84. }
  85. void ShellSort(int *a, int n, bool(*cmp)(int,int))
  86. {
  87.     int i,j,tmp;
  88.     int dis=n/2;
  89.     while (dis>0)
  90.     {
  91.         for(i=dis;i<=n-1;i++)
  92.             {
  93.                 tmp=*(a+i);
  94.                 for(j=i; j>= dis&& cmp(tmp,*(a+j-dis)); j-=dis)
  95.                     *(a+j)=*(a+j-dis);
  96.                 *(a+j)=tmp;
  97.             }
  98.         dis/=2;
  99.     }
  100.     return;
  101. }
  102. void Mergesort(int *a, int l, int r ,int *b, bool (*cmp)(int,int))
  103. {
  104.     int i,j,k,m;
  105.     if (r!=l)
  106.     {
  107.         m=(r+l)/2;
  108.         Mergesort(a,l,m,b,cmp);
  109.         Mergesort(a,m+1,r,b,cmp);
  110.         for(i=m; i>=l;i--) *(b+i)=*(a+i);
  111.         for(j=m+1;j<=r;j++) *(b+r+m+1-j)=*(a+j);
  112.         i++;
  113.         j--;
  114.         for(k=l;k<=r;k++) //
  115.          if (cmp(*(b+i),*(b+j)))
  116.             {*(a+k)=*(b+i); i++;}
  117.             else
  118.             {*(a+k)=*(b+j); j--;}
  119.     }
  120.     return;
  121. }
  122. void Quick_sort(int *a, int l, int r,bool (*cmp)(int, int))
  123. {
  124.     int key = *(a + (l + r) / 2);
  125.     int i,j;
  126.     i=l;
  127.     j=r;
  128.     while (i <= j)
  129.     {
  130.         while (!cmp( key,*(a + i)) && *(a + i) != key) i++;
  131.         while (cmp(key,*(a + j))) j--;
  132.         if (i <= j)
  133.         {
  134.            SWAP(a+i,a+j);
  135.             i++;
  136.             j--;
  137.         }
  138.     }
  139.     if (l<i) Quick_sort(a, l, j,cmp);
  140.     if (i<r) Quick_sort(a, i, r,cmp);
  141. }
  142. void inarr2dim(int **a,int n,int m)
  143. {
  144.     int i,j;
  145.     for(i=0;i<=n-1;i++)
  146.     for(j=0;j<=m-1;j++)
  147.     cin>>*(*(a+i)+j);
  148.     return;
  149. }
  150. void outarr2dim(int **a,int n, int m)
  151. {
  152.     int i,j;
  153.     for(i=0;i<=n-1;i++)
  154.     {
  155.     for(j=0;j<=m-1;j++)
  156.     cout<<*(*(a+i)+j)<<" ";
  157.     cout<<endl;
  158.     }
  159.     return;
  160. }
  161. int LinearSearch(int *a, int n, int val)
  162. {
  163.     int i;
  164.     for(i=0;i<=n-1;i++)
  165.     if (a[i]==val) return i;
  166.     return -1;
  167. }
  168. int BinSearch(int *a, int l,int r, int val)
  169. {
  170.     int mid,res;
  171.     res=-1;
  172.     while (l<=r)
  173.     {
  174.             mid=(l+r)/2;
  175.             //cout<<mid<<" "<<a[mid]<<endl;
  176.             if (*(a+mid)==val) return mid;
  177.             if (*(a+mid)>val) r=mid-1;
  178.             else l=mid+1;
  179.     }
  180.     return res;
  181. }
  182. int InterpolationSearch(int *a, int l, int r, int val)
  183. {
  184.    
  185.     return;
  186. }
  187. int main(){
  188.     cin>>n;
  189.     int *a,*b;
  190.     a=new int [n];
  191.     b=new int [n];
  192.     input(a,n);
  193.     /*
  194.     insert(a,&n,3,100);
  195.     del(a,&n,1);
  196.     Mergesort(a,0,n-1,b,Lesser);
  197.     output(a,n);
  198.     Quick_sort(a,0,n-1,Greater);
  199.     output(a,n);
  200.     SelectionSort(a,n,Greater);
  201.     output(a,n);
  202.     BubbleSort(a,n,Greater);
  203.     output(a,n);
  204.     InsertionSort(a,n,Greater);
  205.     output(a,n);
  206.     ShellSort(a,n,Greater);    
  207.     output(a,n);
  208.     cout<<LinearSearch(a,n,5);
  209.     cout<<BinSearch(a,0,n,5);
  210.     */
  211.    // output(a,n);
  212.     //SelectionSort(a,n,Greater);
  213.     //output(a,n);
  214.     Mergesort(a,0,n-1,b,Greater);
  215.     output(a,n);
  216.     return 0;
  217. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top