SHARE
TWEET

qsort + bubble + tests2

Dari_ Feb 17th, 2019 (edited) 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <math.h>
  5.  
  6.  
  7. int change = 0;
  8. int comp = 0;
  9.  
  10.  
  11. int compare(double first, double sec)                                                     //операция сравнения без учета знака
  12. {
  13.     comp++;
  14.     if (fabs(first) > fabs(sec))
  15.         return -1;
  16.     else if (fabs(first) == fabs(sec))
  17.         return 0;
  18.     else return 1;
  19. }
  20.  
  21.  
  22. void chan(double *first, double *sec)                                                    //меняем переменные местами
  23. {
  24.     change++;
  25.     double prom = *first;
  26.     *first = *sec;
  27.     *sec = prom;
  28. }
  29.  
  30.  
  31. void bubble_sort(double *lst, int n)
  32. {
  33.     for(int i = 0 ; i < n - 1; i++) {
  34.        for(int j = 0 ; j < n - i - 1 ; j++) {
  35.            if(compare(lst[j], lst[j+1]) == -1) {                                          // сравниваем два соседних элемента
  36.               chan(lst + j, lst + j + 1);                                                 // если они идут в неправильном порядке, то меняем их местами
  37.            }
  38.         }
  39.     }
  40. }
  41.  
  42.  
  43.  
  44. void quick_sort(double *lst, int first, int last)
  45. {
  46.     if (first < last)
  47.     {
  48.         int left = first, right = last;
  49.         double middle = lst[(left + right) / 2];
  50.         do
  51.         {
  52.             while (compare(lst[left], middle) == 1) left++;                                // пока не наткнемся на больший/меньший элемент, двигаем указатель
  53.             while (compare(lst[right], middle) == -1) right--;
  54.             if (left <= right)                                                             // если границы не поменялись местами
  55.             {
  56.                 if (left != right)                                                         // то меняем местами
  57.                     chan(lst + left, lst + right);
  58.                 left++;
  59.                 right--;
  60.             }
  61.         } while (left <= right);
  62.         quick_sort(lst, first, right);                                                     // запускаем алгоритм на не отсортированных частях
  63.         quick_sort(lst, left, last);
  64.     }
  65. }
  66.  
  67. void qck_sort(double *lst, int n)
  68. {
  69.     quick_sort(lst, 0, n - 1);
  70. }
  71.  
  72.  
  73. void check(double *lst, int n)
  74. {
  75.     for (int i = 0; i < n-1; i++)
  76.         if (fabs(lst[i]) > fabs(lst[i + 1])) printf("error1 ");
  77. }
  78.  
  79.  
  80. void generation(void)
  81. {
  82.     srand(time(NULL));
  83.     FILE * bubble = fopen ("bubble.txt", "w");
  84.     FILE * quick = fopen ("quick.txt", "w");
  85.  
  86.  
  87.     for (int i = 10; i <= 10000; i *= 10)
  88.     {                                                                                    //создание 2 массивов, удовлетворяющих условию
  89.         for (int j = 1; j <= 4; j++)
  90.         {
  91.             double *lst = (double *) malloc(sizeof(double) * i);
  92.             if (j == 1)                                                                  //в прямом порядке
  93.             {
  94.                 lst[0] = (double)rand()/(double)(RAND_MAX / 10000);
  95.                 for (int k = 1; k < i; k++)
  96.                     lst[k] = lst[k - 1] + (double)rand()/(double)(RAND_MAX / 10000);
  97.             }
  98.             else if (j == 2)                                                             //в обратном порядке
  99.             {
  100.                 lst[0] = -1000000000 - (double)rand()/(double)(RAND_MAX / 10000);
  101.                 for (int k = 1; k < i; k++)
  102.                     lst[k] = lst[k - 1] + (double)rand()/(double)(130 / 100);
  103.             }
  104.             else                                                                         //произвольном порядке
  105.             {
  106.             for (int k = 0; k < i; k++)
  107.                 lst[k] = -5000 + (double)rand()/(double)(RAND_MAX / 10000);
  108.             }
  109.  
  110.             double *lst2 = (double *) malloc(sizeof(double) * i);
  111.             for (int k = 0; k < i; k++)
  112.                 lst2[k] = lst[k];
  113.  
  114.             bubble_sort(lst, i);
  115.             fprintf(bubble, "bubble: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);
  116.             change = 0;
  117.             comp = 0;
  118.  
  119.             /*
  120.             for (int k = 0; k < i; k++)
  121.                 printf("%lf ", lst[k]);
  122.             printf("\n");
  123.             printf("_\n");
  124.             printf("_\n");
  125.             */
  126.  
  127.             qck_sort(lst2, i);
  128.             fprintf(quick, "quick: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);
  129.  
  130.             /*
  131.             for (int k = 0; k < i; k++)
  132.                 printf("%lf ", lst2[k]);
  133.             printf("\n");
  134.             printf("*\n");
  135.             printf("*\n");
  136.             */
  137.  
  138.             check(lst, i);                                                          //проверка
  139.             check(lst2, i);
  140.  
  141.             change = 0;
  142.             comp = 0;
  143.  
  144.             free(lst);
  145.             free(lst2);
  146.         }
  147.         fprintf(bubble, "\n");
  148.         fprintf(quick, "\n");
  149.     }
  150.     fclose(bubble);
  151.     fclose(quick);
  152. }
  153.  
  154.  
  155. void tests_b(void)                                                                                  //тесты для примера
  156. {
  157.     printf("bubble sort\n");
  158.  
  159.     double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
  160.     bubble_sort(first, 10);
  161.     for (int k = 0; k < 10; k++)
  162.         printf("%lf ", first[k]);
  163.         printf("\n");
  164.  
  165.     double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
  166.     bubble_sort(sec, 10);
  167.     for (int k = 0; k < 10; k++)
  168.         printf("%lf ", sec[k]);
  169.         printf("\n");
  170.  
  171.     double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
  172.     bubble_sort(third, 10);
  173.     for (int k = 0; k < 10; k++)
  174.         printf("%lf ", third[k]);
  175.         printf("\n");
  176.  
  177.     double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
  178.     bubble_sort(four, 10);
  179.     for (int k = 0; k < 10; k++)
  180.         printf("%lf ", four[k]);
  181.         printf("\n");
  182.  
  183.     double fith[11] = {3.6, 4.1, 5.3, 2.8, 6.8, 10.8, 7.4, 8.5, 1.4, 10.8, 9.9};
  184.     bubble_sort(fith, 11);
  185.     for (int k = 0; k < 11; k++)
  186.         printf("%lf ", fith[k]);
  187.         printf("\n");
  188.  
  189.     double six[11] = {-3.6, -4.1, -5.3, -2.8, -6.8, -10.8, -7.4, -8.5, -1.4, -10.8, -9.9};
  190.     bubble_sort(six, 11);
  191.     for (int k = 0; k < 11; k++)
  192.         printf("%lf ", six[k]);
  193.         printf("\n");
  194.  
  195.     double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
  196.     bubble_sort(seven, 10);
  197.     for (int k = 0; k < 10; k++)
  198.         printf("%lf ", seven[k]);
  199.         printf("\n");
  200.  
  201.     double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
  202.     bubble_sort(eight, 10);
  203.     for (int k = 0; k < 10; k++)
  204.         printf("%lf ", eight[k]);
  205.         printf("\n");
  206.  
  207.     double nine[11] = {3.6, -4.1, -5.3, 2.8, -6.8, 10.8, -7.4, 8.5, -1.4, -10.8, 9.9};
  208.     bubble_sort(nine, 11);
  209.     for (int k = 0; k < 11; k++)
  210.         printf("%lf ", nine[k]);
  211.         printf("\n");
  212.  
  213.     double ten[11] = {-3.6, 4.1, 5.3, 2.8, -6.8, 10.8, 7.4, -8.5, -1.4, 10.8, -9.9};
  214.     bubble_sort(ten, 11);
  215.     for (int k = 0; k < 11; k++)
  216.         printf("%lf ", ten[k]);
  217.         printf("\n");
  218.  
  219.     printf("\n");
  220.     printf("\n");
  221.  
  222. }
  223.  
  224.  
  225. void tests_q(void)
  226. {
  227.     printf("quick sort\n");
  228.  
  229.     double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
  230.     qck_sort(first, 10);
  231.     for (int k = 0; k < 10; k++)
  232.         printf("%lf ", first[k]);
  233.         printf("\n");
  234.  
  235.     double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
  236.     qck_sort(sec, 10);
  237.     for (int k = 0; k < 10; k++)
  238.         printf("%lf ", sec[k]);
  239.         printf("\n");
  240.  
  241.     double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
  242.     qck_sort(third, 10);
  243.     for (int k = 0; k < 10; k++)
  244.         printf("%lf ", third[k]);
  245.         printf("\n");
  246.  
  247.     double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
  248.     qck_sort(four, 10);
  249.     for (int k = 0; k < 10; k++)
  250.         printf("%lf ", four[k]);
  251.         printf("\n");
  252.  
  253.     double fith[11] = {3.6, 4.1, 5.3, 2.8, 6.8, 10.8, 7.4, 8.5, 1.4, 10.8, 9.9};
  254.     qck_sort(fith, 11);
  255.     for (int k = 0; k < 11; k++)
  256.         printf("%lf ", fith[k]);
  257.         printf("\n");
  258.  
  259.     double six[11] = {-3.6, -4.1, -5.3, -2.8, -6.8, -10.8, -7.4, -8.5, -1.4, -10.8, -9.9};
  260.     qck_sort(six, 11);
  261.     for (int k = 0; k < 11; k++)
  262.         printf("%lf ", six[k]);
  263.         printf("\n");
  264.  
  265.     double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
  266.     qck_sort(seven, 10);
  267.     for (int k = 0; k < 10; k++)
  268.         printf("%lf ", seven[k]);
  269.         printf("\n");
  270.  
  271.     double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
  272.     qck_sort(eight, 10);
  273.     for (int k = 0; k < 10; k++)
  274.         printf("%lf ", eight[k]);
  275.         printf("\n");
  276.  
  277.     double nine[11] = {3.6, -4.1, -5.3, 2.8, -6.8, 10.8, -7.4, 8.5, -1.4, -10.8, 9.9};
  278.     qck_sort(nine, 11);
  279.     for (int k = 0; k < 11; k++)
  280.         printf("%lf ", nine[k]);
  281.         printf("\n");
  282.  
  283.     double ten[11] = {-3.6, 4.1, 5.3, 2.8, -6.8, 10.8, 7.4, -8.5, -1.4, 10.8, -9.9};
  284.     qck_sort(ten, 11);
  285.     for (int k = 0; k < 11; k++)
  286.         printf("%lf ", ten[k]);
  287.         printf("\n");
  288.  
  289.     printf("\n");
  290. }
  291.  
  292.  
  293. int main(void)
  294. {
  295.     generation();
  296.     tests_b();
  297.     tests_q();
  298.     return 0;
  299. }
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