daily pastebin goal
19%
SHARE
TWEET

Untitled

a guest Jan 17th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. int g=0;
  3.  
  4. int tab11[30];
  5. int tab12[30];
  6. int tab21[30];
  7. int tab22[30];
  8. int tab31[30];
  9. int tab32[30];
  10. int tab41[30];
  11. int tab42[30];
  12.  
  13. int qpor=0;
  14. int qpods=0;
  15. void druk(int a[], int n)
  16. {
  17.     int i=0;
  18.     for(i;i<n;i++)
  19.     {
  20.         printf("%i ",a[i]);
  21.     }
  22.     printf("\n");
  23. }
  24. void losu(int a[], int n)
  25. {
  26.     srand(time(NULL));
  27.     int i=0;
  28.     for(i;i<n;i++)
  29.     {
  30.         a[i]=rand()%n;
  31.     }
  32. }
  33. void kopiuj(int a[],int b[],int n)
  34. {
  35.     int i=0;
  36.     for(i;i<n;i++)
  37.     {
  38.         b[i]=a[i];
  39.     }
  40. }
  41. void wstawianie(int a[],int n)
  42. {
  43.     unsigned long long int por=0;
  44.     unsigned long long int pods=0;
  45.     int i,j,x;
  46.     for(i=1;i<n;i++)
  47.     {
  48.         por++;
  49.         if(a[i]<a[0])
  50.         {
  51.             pods=pods+2;
  52.             x=a[0];
  53.             a[0]=a[i];
  54.         }
  55.         else
  56.         {
  57.             pods++;
  58.             x=a[i];
  59.         }
  60.        
  61.         for(j=i-1;x<a[j];j--)
  62.         {
  63.             por++;
  64.             a[j+1]=a[j];
  65.             pods++;
  66.         }
  67.         pods++;
  68.         a[j+1]=x;  
  69.     }
  70.     tab21[g]=por;
  71.     tab22[g]=pods;
  72.     //printf("Sortowanie przez wstawianie porownania - %i , podstawienia - %i\n",pods,pods);
  73. }
  74. void babelkowe(int a[],int n)
  75. {
  76.     unsigned int por=0;
  77.     unsigned int pods=0;
  78.     int i,j,x;
  79.     for(i=1;i<n;i++)
  80.     {
  81.         for(j=n-1;j>=i;j--)
  82.         {
  83.             por++;
  84.             if(a[j-1]>a[j])
  85.             {
  86.                 //SPRAWDŹ CAŁY PROGRAM TAK OOOO
  87.                 pods+=3;
  88.                 x=a[j-1];
  89.                 a[j-1]=a[j];
  90.                 a[j]=x;
  91.             }
  92.         }
  93.     }
  94.     tab11[g]=por;
  95.     tab12[g]=pods;
  96.     //printf("Sortowanie babelkowe porownania - %i , podstawienia - %i\n",por,pods);
  97. }
  98.  
  99. int Partition(int a[],int p, int r)
  100. {
  101.     int _r=rand()%(r-p+1)+p,x,i,j;
  102.     qpods=qpods+5;
  103.     x=a[p];
  104.     a[p]=a[_r];
  105.     a[_r]=x;
  106.     x=a[p];
  107.     i=p-1;
  108.     j=r+1;
  109.    
  110.     do
  111.     {
  112.         do
  113.         {
  114.             j--;
  115.             qpor++;
  116.         }while(a[j]>x);
  117.         do
  118.         {
  119.             qpor++;
  120.             i++;
  121.         }while(a[i]<x);
  122.         if(i<j)
  123.         {
  124.             qpods=qpods+3;
  125.             int y;
  126.             y=a[i];
  127.             a[i]=a[j];
  128.             a[j]=y;
  129.         }
  130.     }while(i<j);
  131.     return j;
  132. }
  133. void QSort(int a[],int p,int r)
  134. {
  135.     int q;
  136.     if(p<r)
  137.     {
  138.         q=Partition(a,p,r);
  139.         QSort(a,p,q);
  140.         QSort(a,q+1,r);
  141.     }
  142. }
  143. void shell(int d[],int n)
  144. {
  145.     int por=0;
  146.     int pods=0;
  147.     int h,j,x,i;
  148.     for(h=1;h<n;h=3*h+1);
  149.     h/=9;
  150.     while(h)
  151.     {
  152.         for(j=n-h-1;j>=0;j--)
  153.         {
  154.             pods++;
  155.             x = d[j];
  156.             i = j + h;
  157.             while((i<n) && (x>d[i]))
  158.             {
  159.                 por=por+2;
  160.                 pods++;
  161.                 d[i-h] = d[i];
  162.                 i+=h;
  163.             }
  164.         pods++;
  165.         d[i-h]=x;
  166.         }
  167.         h/=3;
  168.     }
  169.     tab41[g]=por;
  170.     tab42[g]=pods;
  171.     //printf("Sortowanie metoda Shella porownania - %i , podstawienia - %i\n",por,pods);   
  172. }
  173. int main()
  174. {
  175.     int n;
  176.     for(n=100;n<1000000;)
  177.     {
  178.     int i=0;
  179.     int tab[n];
  180.     int tab1[n];
  181.     int tab2[n];
  182.     int tab3[n];
  183.     for(i=0;i<30;i++)
  184.     {
  185.         losu(tab,n);
  186.         kopiuj(tab,tab1,n);
  187.         kopiuj(tab,tab2,n);
  188.         kopiuj(tab,tab3,n);
  189.         babelkowe(tab,n);
  190.         wstawianie(tab1,n);
  191.         QSort(tab2,n/2,n);
  192.        
  193.         tab31[i]=qpor;
  194.         tab32[i]=qpods;
  195.         //printf("Szybkie sortowanie porownania - %i , podstawienia - %i\n",qpor,qpods);
  196.         qpor=0;
  197.         qpods=0;
  198.         shell(tab3,n);
  199.         g++;
  200.     }
  201.     i=0;
  202.     unsigned long long int sumapor1=0;
  203.     unsigned long long int sumapod1=0;
  204.     unsigned long long int sumapor2=0;
  205.     unsigned long long int sumapod2=0;
  206.     unsigned long long int sumapor3=0;
  207.     unsigned long long int sumapod3=0;
  208.     unsigned long long int sumapor4=0;
  209.     unsigned long long int sumapod4=0;
  210.     for(i=0;i<30;i++)
  211.     {
  212.         sumapor1+=tab11[i];
  213.         sumapod1+=tab12[i];
  214.         sumapor2+=tab21[i];
  215.         sumapod2+=tab22[i];
  216.         sumapor3+=tab31[i];
  217.         sumapod3+=tab32[i];
  218.         sumapor4+=tab41[i];
  219.         sumapod4+=tab42[i];
  220.     }
  221.     sumapor1=sumapor1/30;
  222.     sumapod1=sumapod1/30;
  223.     sumapor2=sumapor2/30;
  224.     sumapod2=sumapod2/30;
  225.     sumapor3=sumapor3/30;
  226.     sumapod3=sumapod3/30;
  227.     sumapor4=sumapor4/30;
  228.     sumapod4=sumapod4/30;
  229.     printf("Sposoby kolejno: babelkowe, wstawianie, QSort, Shell\nPorownania - podstawienia - n\n");
  230.     printf("%d - %d - %d\n",sumapor1,sumapod1,n);
  231.     printf("%d - %d - %d\n",sumapor2,sumapod2,n);
  232.     printf("%d - %d - %d\n",sumapor3,sumapod3,n);
  233.     printf("%d - %d - %d\n",sumapor4,sumapod4,n);
  234.     /*
  235.     losu(tab1,n);
  236.     kopiuj(tab1,tab2,n);
  237.     kopiuj(tab1,tab3,n);
  238.     kopiuj(tab1,tab4,n);
  239.    
  240.     //druk(tab1,n);
  241.     babelkowe(tab1,n);
  242.     //druk(tab1,n);
  243.    
  244.     //druk(tab2,n);
  245.     wstawianie(tab2,n);
  246.     //druk(tab2,n);
  247.    
  248.     //druk(tab3,n);
  249.     QSort(tab3,n/2,n);
  250.     //druk(tab3,n);
  251.    
  252.     //druk(tab4,n);
  253.     shell(tab4,n);
  254.     //druk(tab4,n);
  255.    
  256.    
  257.     */
  258.     if(n<1000) n=n+100;
  259.     else
  260.     {
  261.         if(n<10000) n=n+10000;
  262.         else
  263.         {
  264.             if(n<100000)
  265.             n=n+10000;
  266.             else n=n+100000;
  267.         }
  268.     }
  269.     g=0;
  270.     }
  271.     return 0;
  272. }
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
 
Top