SHARE
TWEET

qsort + bubble + tests

Dari_ Feb 17th, 2019 15 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. void check_compare(double *first, double *sec, int n)
  73. {
  74.     for (int i = 0; i < n; i++)
  75.         if (first[i] != sec[i]) printf("error");
  76. }
  77.  
  78. void check(double *lst, int n)
  79. {
  80.     for (int i = 0; i < n-1; i++)
  81.         if (fabs(lst[i]) > fabs(lst[i + 1])) printf("error");
  82. }
  83.  
  84.  
  85. void generation(void)
  86. {
  87.     srand(time(NULL));
  88.     FILE * bubble = fopen ("bubble.txt", "w");
  89.     FILE * quick = fopen ("quick.txt", "w");
  90.  
  91.  
  92.     for (int i = 1; i <= 10; i++)
  93.     {                                                                                    //создание 2 массивов, удовлетворяющих условию
  94.         for (int j = 1; j <= 4; j++)
  95.         {
  96.             double *lst = (double *) malloc(sizeof(double) * i);
  97.             if (j == 1)                                                                  //в прямом порядке
  98.             {
  99.                 lst[0] = (double)rand()/(double)(RAND_MAX / 10000);
  100.                 for (int k = 1; k < i; k++)
  101.                     lst[k] = lst[k - 1] + (double)rand()/(double)(RAND_MAX / 10000);
  102.             }
  103.             else if (j == 2)                                                             //в обратном порядке
  104.             {
  105.                 lst[0] = -1000000000 - (double)rand()/(double)(RAND_MAX / 10000);
  106.                 for (int k = 1; k < i; k++)
  107.                     lst[k] = lst[k - 1] + (double)rand()/(double)(130 / 100);
  108.             }
  109.             else                                                                         //произвольном порядке
  110.             {
  111.             for (int k = 0; k < i; k++)
  112.                 lst[k] = -5000 + (double)rand()/(double)(RAND_MAX / 10000);
  113.             }
  114.  
  115.             double *lst2 = (double *) malloc(sizeof(double) * i);
  116.             for (int k = 0; k < i; k++)
  117.                 lst2[k] = lst[k];
  118.  
  119.             bubble_sort(lst, i);
  120.             fprintf(bubble, "bubble: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);
  121.             change = 0;
  122.             comp = 0;
  123.  
  124.             /*
  125.             for (int k = 0; k < i; k++)
  126.                 printf("%lf ", lst[k]);
  127.             printf("\n");
  128.             printf("_\n");
  129.             printf("_\n");
  130.             */
  131.  
  132.             qck_sort(lst2, i);
  133.             fprintf(quick, "quick: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);
  134.  
  135.             /*
  136.             for (int k = 0; k < i; k++)
  137.                 printf("%lf ", lst2[k]);
  138.             printf("\n");
  139.             printf("*\n");
  140.             printf("*\n");
  141.             */
  142.  
  143.             check(lst, i);                                                          //проверка
  144.             check(lst2, i);
  145.             check_compare(lst, lst2, i);
  146.  
  147.             change = 0;
  148.             comp = 0;
  149.  
  150.             free(lst);
  151.             free(lst2);
  152.         }
  153.         fprintf(bubble, "\n");
  154.         fprintf(quick, "\n");
  155.     }
  156.     fclose(bubble);
  157.     fclose(quick);
  158. }
  159.  
  160.  
  161. void tests_b(void)                                                                                  //тесты для примера
  162. {
  163.     printf("bubble sort\n");
  164.  
  165.     double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
  166.     bubble_sort(first, 10);
  167.     for (int k = 0; k < 10; k++)
  168.         printf("%lf ", first[k]);
  169.         printf("\n");
  170.  
  171.     double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
  172.     bubble_sort(sec, 10);
  173.     for (int k = 0; k < 10; k++)
  174.         printf("%lf ", sec[k]);
  175.         printf("\n");
  176.  
  177.     double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
  178.     bubble_sort(third, 10);
  179.     for (int k = 0; k < 10; k++)
  180.         printf("%lf ", third[k]);
  181.         printf("\n");
  182.  
  183.     double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
  184.     bubble_sort(four, 10);
  185.     for (int k = 0; k < 10; k++)
  186.         printf("%lf ", four[k]);
  187.         printf("\n");
  188.  
  189.     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};
  190.     bubble_sort(fith, 11);
  191.     for (int k = 0; k < 11; k++)
  192.         printf("%lf ", fith[k]);
  193.         printf("\n");
  194.  
  195.     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};
  196.     bubble_sort(six, 11);
  197.     for (int k = 0; k < 11; k++)
  198.         printf("%lf ", six[k]);
  199.         printf("\n");
  200.  
  201.     double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
  202.     bubble_sort(seven, 10);
  203.     for (int k = 0; k < 10; k++)
  204.         printf("%lf ", seven[k]);
  205.         printf("\n");
  206.  
  207.     double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
  208.     bubble_sort(eight, 10);
  209.     for (int k = 0; k < 10; k++)
  210.         printf("%lf ", eight[k]);
  211.         printf("\n");
  212.  
  213.     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};
  214.     bubble_sort(nine, 11);
  215.     for (int k = 0; k < 11; k++)
  216.         printf("%lf ", nine[k]);
  217.         printf("\n");
  218.  
  219.     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};
  220.     bubble_sort(ten, 11);
  221.     for (int k = 0; k < 11; k++)
  222.         printf("%lf ", ten[k]);
  223.         printf("\n");
  224.  
  225.     printf("\n");
  226.     printf("\n");
  227.  
  228. }
  229.  
  230.  
  231. void tests_q(void)
  232. {
  233.     printf("quick sort\n");
  234.  
  235.     double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
  236.     qck_sort(first, 10);
  237.     for (int k = 0; k < 10; k++)
  238.         printf("%lf ", first[k]);
  239.         printf("\n");
  240.  
  241.     double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
  242.     qck_sort(sec, 10);
  243.     for (int k = 0; k < 10; k++)
  244.         printf("%lf ", sec[k]);
  245.         printf("\n");
  246.  
  247.     double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
  248.     qck_sort(third, 10);
  249.     for (int k = 0; k < 10; k++)
  250.         printf("%lf ", third[k]);
  251.         printf("\n");
  252.  
  253.     double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
  254.     qck_sort(four, 10);
  255.     for (int k = 0; k < 10; k++)
  256.         printf("%lf ", four[k]);
  257.         printf("\n");
  258.  
  259.     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};
  260.     qck_sort(fith, 11);
  261.     for (int k = 0; k < 11; k++)
  262.         printf("%lf ", fith[k]);
  263.         printf("\n");
  264.  
  265.     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};
  266.     qck_sort(six, 11);
  267.     for (int k = 0; k < 11; k++)
  268.         printf("%lf ", six[k]);
  269.         printf("\n");
  270.  
  271.     double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
  272.     qck_sort(seven, 10);
  273.     for (int k = 0; k < 10; k++)
  274.         printf("%lf ", seven[k]);
  275.         printf("\n");
  276.  
  277.     double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
  278.     qck_sort(eight, 10);
  279.     for (int k = 0; k < 10; k++)
  280.         printf("%lf ", eight[k]);
  281.         printf("\n");
  282.  
  283.     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};
  284.     qck_sort(nine, 11);
  285.     for (int k = 0; k < 11; k++)
  286.         printf("%lf ", nine[k]);
  287.         printf("\n");
  288.  
  289.     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};
  290.     qck_sort(ten, 11);
  291.     for (int k = 0; k < 11; k++)
  292.         printf("%lf ", ten[k]);
  293.         printf("\n");
  294.  
  295.     printf("\n");
  296. }
  297.  
  298.  
  299. int main(void)
  300. {
  301.     generation();
  302.     tests_b();
  303.     tests_q();
  304.     return 0;
  305. }
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