daily pastebin goal
86%
SHARE
TWEET

Untitled

a guest Nov 22nd, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define R 100
  4. #define RAND(R) rand()%R
  5. #define N 10
  6. #define CNT_PRN printf ("\ncnt_cnp=%lld cnt_cpy=%lld\n",cnt_cmp, cnt_cpy)
  7.  
  8. long long cnt_cmp, cnt_cpy;
  9.  
  10. int best_array(int a[],int n);
  11. int awg_array(int a[],int n,int k);
  12. int worst_array(int a[],int n);
  13. int printf_array(int a[],int n);
  14. int selection_sort(int a[], int n);
  15. int bubble_sort(int a[], int n);
  16. int max_heapify(int a[], int i, int n);
  17. int build_max_heap(int a[], int n);
  18. int heapsort(int a[], int n);
  19. int countingsort(int a[], int n);
  20.  
  21. int main()
  22. {
  23.   int array[N];
  24.   best_array(array,N);
  25.   printf_array(array,N);
  26.   awg_array(array,N,10);
  27.   worst_array(array,N);
  28.   printf_array(array,N);
  29.   bubble_sort(array,N);
  30.   heapsort(array, N);
  31.   countingsort(array, N);
  32.   CNT_PRN;
  33.   printf_array(array,N);
  34.   return 0;
  35. }
  36.  
  37. int best_array(int a[],int n)
  38. {
  39.   int i;
  40.   for(i=0;i<n;i++) a[i]=i;
  41.   return i;
  42. }
  43.  
  44. int worst_array(int a[],int n)
  45. {
  46.   int i;
  47.   for(i=0;i<n;i++) a[i]=n-1-i;
  48.   return i;
  49. }
  50.  
  51. int awg_array(int a[],int n,int k)
  52. {
  53.   int i,j;
  54.   for(j=1;j<=k;j++)
  55.   {
  56.       srand(j);
  57.     for(i=0;i<n;i++) a[i]=RAND(R);
  58.     printf_array(a,n);
  59.   }
  60.   return j;
  61. }
  62.  
  63. int printf_array(int *a,int n)
  64. {
  65.   int i;
  66.   for(i=0;i<n;i++) printf("%d\t",a[i]);
  67.   printf("\n\n");
  68.   return i;
  69. }
  70.  
  71. int selection_sort(int a[], int n)
  72. {
  73.     int i, S, j, min;
  74.     for(S=0; S<=n-1; S++)
  75.     {
  76.     min=a[S];
  77.     j=S;
  78.         for(i=S+1; i<=n-1; i++)
  79.         {
  80.             if(min>a[i])
  81.             {
  82.                 min=a[i];
  83.                 j=i;
  84.             }          
  85.         }
  86.         a[j]=a[S];
  87.         a[S]=min;
  88.     }
  89.     return min;
  90. }
  91.  
  92. int bubble_sort(int a[], int n)
  93. {
  94. // 
  95.     int k, i, temp;
  96.     for(k=n-2; k>=0; k--)
  97.     {
  98.         for(i=0; i<=k; i++)
  99.         {
  100.             cnt_cmp++;
  101.             if(a[i]>a[i+1])
  102.             {
  103.                 temp=a[i];
  104.                 a[i]=a[i+1];
  105.                 a[i+1]=temp;
  106.                 cnt_cpy+=3;
  107.             }
  108.         }
  109.     }
  110. // 
  111. }
  112.  
  113. int max_heapify(int a[], int i, int n)
  114. {
  115.     int left, right, largest, temp;
  116.     left=2*(i+1)-1;
  117.     right=2*(i+1);
  118.     if ((left<n)&&(a[left]<a[i]))
  119.     {
  120.         largest=left;
  121.     }
  122.     else
  123.     {
  124.         largest=i;
  125.     }
  126.     if((right<n)&&(a[right]>a[largest]))
  127.     {
  128.         largest=right;
  129.     }
  130.     if (largest!=i)
  131.     {
  132.         temp=a[i];
  133.         a[i]=a[largest];
  134.         a[largest]=temp;
  135.         max_heapify(a, largest, n);
  136.     }
  137.     return i;
  138. }
  139.  
  140. int build_max_heap(int a[], int n)
  141. {
  142.     int i;
  143.     i=n/2;
  144.     for(i=n/2; i>=0; i--)
  145.     {
  146.         max_heapify(a, i, n);
  147.     }
  148.     return 1;
  149. }
  150.  
  151. int heapsort(int a[], int n)
  152. {
  153.     int temp, i, heap_size;
  154.     build_max_heap(a, n);
  155.     heap_size=n;
  156.     i=n-1;
  157.     while (i>0)
  158.     {
  159.         temp=a[0];
  160.         a[0]=a[i];
  161.         a[i]=temp;
  162.         heap_size=heap_size-1;
  163.         max_heapify(a, 0, heap_size);
  164.         i--;   
  165.     }
  166.     return a[i];
  167. }
  168.  
  169.  
  170. int countingsort(int a[], int n)
  171. {
  172.     int b[N], c[N];
  173.     int i, j, k;
  174.     k=10;
  175.     for(i=0; i<k; i++)
  176.     {
  177.         c[i]=0;
  178.     }
  179.     for(j=0; j<n; j++)
  180.     {
  181.         c[a[j]]++;
  182.     }
  183.     for(i=1; i<k; i++)
  184.     {
  185.         c[i]=c[i]+c[i-1];
  186.     }
  187.     for(j=n-1; j>=0; j--)
  188.     {
  189.         b[c[a[j]]]=a[j];
  190.         c[a[j]]--;
  191.     }
  192.     return b[c[a[j]]];
  193. }
RAW Paste Data
Top