SHARE
TWEET

Untitled

a guest Apr 21st, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <windows.h>
  8. #include <malloc.h>
  9.  
  10. enum SortsType
  11. {
  12.     BUBBLE,
  13.     SELECTION,
  14.     INSERTS,
  15.     SHELL,
  16.     QUICK
  17. };
  18.  
  19. #undef max
  20.  
  21. int **INITIAL;
  22. int **WORK;
  23.  
  24. int n, m;
  25.  
  26. unsigned permutations[5];
  27. unsigned comparisions[5];
  28.  
  29. unsigned SumOfNumbers(int elem);
  30.  
  31. void BubbleSort();
  32. void SelectionSort();
  33. void InsertsSort();
  34. void ShellSort();
  35. void QuickSort(int** arr, unsigned column, int left, int right);
  36.  
  37. void ShowRetry();
  38.  
  39. void main()
  40. {
  41. begin:  for (;;)
  42.     {
  43.         std::cout << "Enter \"n\" and \"m\" between 1 and 15" << std::endl;
  44.         std::cout << "n =  ";
  45.         if (!(std::cin >> n) || n < 1 || n > 15)
  46.         {
  47.             std::cin.clear();
  48.             std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  49.             std::cout << "Error! Incorrect number" << std::endl;
  50.             continue;
  51.         }
  52.         std::cout << "m = ";
  53.         if (!(std::cin >> m) || m < 1 || m > 15)
  54.         {
  55.             std::cin.clear();
  56.             std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  57.             std::cout << "Error! Incorrect number" << std::endl;
  58.             continue;
  59.         }
  60.         break;
  61.     }
  62.     srand(time(0));
  63.     INITIAL = new int*[n];
  64.     WORK = new int*[n];
  65.     for (int i = 0; i < n; i++)
  66.     {
  67.         INITIAL[i] = new int[m];
  68.         WORK[i] = new int[m];
  69.         for (int j = 0; j < m; j++)
  70.         {
  71.             INITIAL[i][j] = rand() % 201 - 100;
  72.             WORK[i][j] = INITIAL[i][j];
  73.         }
  74.     }
  75.     std::cout << "\nInitial array:\n" << std::endl;
  76.     ShowRetry();
  77.     BubbleSort();
  78.     std::cout << "\nBubble:\n" << std::endl;
  79.     ShowRetry();
  80.     SelectionSort();
  81.     std::cout << "\nSelection:\n" << std::endl;
  82.     ShowRetry();
  83.     InsertsSort();
  84.     std::cout << "\nInserts:\n" << std::endl;
  85.     ShowRetry();
  86.     ShellSort();
  87.     std::cout << "\nShell:\n" << std::endl;
  88.     ShowRetry();
  89.     for (int j = 0; j < m; j++)
  90.         QuickSort(WORK, j, 0, n - 1);
  91.     std::cout << "\nQuick:\n" << std::endl;
  92.     ShowRetry();
  93.     printf("\n--------------------------------------------\n");
  94.     printf("|%10s|%15s|%15s|\n", "Method", "Permutations", "Comparisons");
  95.     printf("--------------------------------------------\n");
  96.     printf("|%10s|%15d|%15d|\n", "Bubble", permutations[BUBBLE], comparisions[BUBBLE]);
  97.     printf("|%10s|%15d|%15d|\n", "Selection", permutations[SELECTION], comparisions[SELECTION]);
  98.     printf("|%10s|%15d|%15d|\n", "Inserts", permutations[INSERTS], comparisions[INSERTS]);
  99.     printf("|%10s|%15d|%15d|\n", "Shell", permutations[SHELL], comparisions[SHELL]);
  100.     printf("|%10s|%15d|%15d|\n", "Quick", permutations[QUICK], comparisions[QUICK]);
  101.     printf("--------------------------------------------\n");
  102. rep:    std::cout << "\nRepeat? 0 - no, 1 - yes" << std::endl;
  103.     short repeat = -1;
  104.     std::cin >> repeat;
  105.     if ((repeat == 1) || (repeat == 0))
  106.     {
  107.         if (repeat == 1)
  108.         {
  109.             memset(permutations, 0, sizeof(unsigned) * 5);
  110.             memset(comparisions, 0, sizeof(unsigned) * 5);
  111.             goto begin;
  112.         }
  113.     }
  114.     else
  115.     {
  116.         std::cin.clear();
  117.         std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  118.         std::cout << "\nError! Incorrect number\n" << std::endl;
  119.         goto rep;
  120.     }
  121. }
  122.  
  123. unsigned SumOfNumbers(int elem)
  124. {
  125.     elem = abs(elem);
  126.     if (elem == 0)
  127.         return 0;
  128.     return SumOfNumbers(elem / 10) + (elem % 10);
  129. }
  130.  
  131. void BubbleSort()
  132. {
  133.     bool flag;
  134.     for (int j = 0; j < m; j++)
  135.     {
  136.         for (int k = 0; k < n - 1; ++k)
  137.         {
  138.             flag = false;
  139.             for (int i = 0; i < n - k - 1; i++)
  140.             {
  141.                 if (SumOfNumbers(WORK[i][j]) > SumOfNumbers(WORK[i + 1][j]))
  142.                 {
  143.                     std::swap(WORK[i][j], WORK[i + 1][j]);
  144.                     ++permutations[BUBBLE];
  145.                     flag = true;
  146.                 }
  147.                 ++comparisions[BUBBLE];
  148.             }
  149.             if (!flag) break;
  150.         }
  151.     }
  152. }
  153. void SelectionSort()
  154. {
  155.     int minimum, index;
  156.     for (int j = 0; j < m; j++)
  157.         for (int i = 0; i < n - 1; i++)
  158.         {
  159.             minimum = WORK[i][j];
  160.             index = i;
  161.             for (int k = i + 1; k < n; ++k)
  162.             {
  163.                 ++comparisions[SELECTION];
  164.                 if (SumOfNumbers(minimum) > SumOfNumbers(WORK[k][j]))
  165.                 {
  166.                     minimum = WORK[k][j];
  167.                     index = k;
  168.                 }
  169.             }
  170.             if (i != index)
  171.             {
  172.                 std::swap(WORK[i][j], WORK[index][j]);
  173.                 ++permutations[SELECTION];
  174.             }
  175.         }
  176. }
  177. void InsertsSort()
  178. {
  179.     int k, tmp;
  180.     for (int j = 0; j < m; j++)
  181.         for (int i = 1; i < n; i++)
  182.         {
  183.             tmp = WORK[i][j];
  184.             for (k = i - 1; k >= 0; k--)
  185.             {
  186.                 ++comparisions[INSERTS];
  187.                 if (SumOfNumbers(tmp) >= SumOfNumbers(WORK[k][j]))
  188.                     break;
  189.                 WORK[k + 1][j] = WORK[k][j];
  190.             }
  191.             if (i != k + 1)
  192.             {
  193.                 WORK[k + 1][j] = tmp;
  194.                 ++permutations[INSERTS];
  195.             }
  196.         }
  197. }
  198. void ShellSort()
  199. {
  200.     int tmp, step;
  201.     for (int j = 0; j < m; j++)
  202.         for (step = (n / 2) + (n % 2); step > 0; --step)
  203.             for (int k = 0; k < n - step; ++k)
  204.             {
  205.                 if (SumOfNumbers(WORK[k][j]) > SumOfNumbers(WORK[k + step][j]))
  206.                 {
  207.                     std::swap(WORK[k][j], WORK[k + step][j]);
  208.                     ++permutations[SHELL];
  209.                 }
  210.                 ++comparisions[SHELL];
  211.             }
  212. }
  213.  
  214. void QuickSort(int** arr, unsigned column, int left, int right)
  215. {
  216.     int i = left, j = right;
  217.     const unsigned idx = (left + right) / 2;
  218.     int avg = arr[idx][column];
  219.     while (i <= j)
  220.     {
  221.         while (SumOfNumbers(arr[i][column]) < SumOfNumbers(avg))
  222.         {
  223.             if (idx != i)
  224.                 ++comparisions[QUICK];
  225.             ++i;
  226.         }
  227.         if (idx != i)
  228.             ++comparisions[QUICK];
  229.         while (SumOfNumbers(arr[j][column]) > SumOfNumbers(avg))
  230.         {
  231.             if (idx != j)
  232.                 ++comparisions[QUICK];
  233.             --j;
  234.         }
  235.         if (idx != j)
  236.             ++comparisions[QUICK];
  237.         if (i <= j)
  238.         {
  239.             if (i != j)
  240.                 ++permutations[QUICK];
  241.             std::swap(arr[i][column], arr[j][column]);
  242.             ++i;
  243.             --j;
  244.         }
  245.     };
  246.     if (left < j)
  247.         QuickSort(arr, column, left, j);
  248.     if (i < right)
  249.         QuickSort(arr, column, i, right);
  250. }
  251.  
  252. void ShowRetry()
  253. {
  254.     for (int i = 0; i < n; i++)
  255.     {
  256.         for (int j = 0; j < m; j++)
  257.         {
  258.             printf("%4d ", WORK[i][j]);
  259.             WORK[i][j] = INITIAL[i][j];
  260.         }
  261.         std::cout << std::endl;
  262.     }
  263. }
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