Advertisement
Bibodui

Sortings

Dec 20th, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <Windows.h>
  3. #include <fstream>
  4. #include <ctime>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. void create_array(int*, int, string);
  10. void output_array(int*, int);
  11. void Exchange(int, int, int*);
  12. void Hoar_Sort(int, int*);
  13. void Quick_Sort(int, int, int*);
  14. void Binary_Pyramid_Sort(int, int*);
  15. void Build_Pyramid(int, int, int*);
  16. void Sort_Piramid(int, int*);
  17. void Sifting(int, int, int*);
  18. void BubbleSort(int, int*);
  19.  
  20. int compare1 = 0;
  21. int replace1 = 0;
  22. int compare2 = 0;
  23. int replace2 = 0;
  24. int compare3 = 0;
  25. int replace3 = 0;
  26.  
  27. int main()
  28. {
  29.     int q;
  30.  
  31.     do
  32.     {
  33.         SetConsoleOutputCP(1251);
  34.         SetConsoleCP(1251);
  35.  
  36.         string s1 = "Sortings_tmp_100.txt";
  37.         string s2 = "Sortings_tmp_1000.txt";
  38.  
  39.         int size_small, size_big;
  40.         cout << "Введите размер малого массива" << endl;
  41.         cin >> size_small;
  42.         cout << "Введите размер большого массива" << endl;
  43.         cin >> size_big;
  44.  
  45.         int* small_array = new int[size_small];
  46.         int* big_array = new int[size_big];
  47.        
  48.         int* small_quick_array = new int[size_small];
  49.         int* big_quick_array = new int[size_big];
  50.  
  51.         int* small_heap_array = new int[size_small];
  52.         int* big_heap_array = new int[size_big];
  53.  
  54.         int* small_bubble_array = new int[size_small];
  55.         int* big_bubble_array = new int[size_big];
  56.        
  57.         create_array(small_array, size_small, s1);
  58.         cout << "Малый массив:" << endl;
  59.         output_array(small_array, size_small);
  60.  
  61.         for (int i = 0; i < size_small; i++)
  62.         {
  63.             small_bubble_array[i] = small_heap_array[i] = small_quick_array[i] = small_array[i];
  64.         }
  65.  
  66.         cout << "Быстрая сортировка Хоара (малый массив):" << endl;
  67.         Hoar_Sort(size_small, small_quick_array);
  68.         output_array(small_quick_array, size_small);
  69.         cout << "Пирамидальная сортировка (малый массив):" << endl;
  70.         Binary_Pyramid_Sort(size_small, small_heap_array);
  71.         output_array(small_heap_array, size_small);
  72.         cout << "Сортировка пузырьком (малый массив):" << endl;
  73.         BubbleSort(size_small, small_bubble_array);
  74.         output_array(small_bubble_array, size_small);
  75.  
  76.         cout << "В быстрой сортировке сравнений: " << compare1 << ", перестановок: " << replace1 << endl;
  77.         cout << "В пирамидальной сортировке сравнений: " << compare2 << ", перестановок: " << replace2 << endl;
  78.         cout << "В сортировке пузырьком сравнений: " << compare3 << ", перестановок: " << replace3 << endl;
  79.  
  80.         if (compare1 < compare2)
  81.             if (compare1 < compare3)
  82.                 cout << "В быстрой сортировке меньше всего сравнений" << endl;
  83.             else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
  84.         else if (compare2 < compare3)
  85.             cout << "В пирамидальной сортировке меньше всего сравнений" << endl;
  86.             else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
  87.  
  88.          if (replace1 < replace2)
  89.             if (replace1 < replace3)
  90.                 cout << "В быстрой сортировке меньше всего перестановок" << endl;
  91.             else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
  92.         else if (replace2 < replace3)
  93.             cout << "В пирамидальной сортировке меньше всего перестановок" << endl;
  94.             else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
  95.  
  96.         compare1 = compare2 = compare3 = replace1 = replace2 = replace3 = 0;
  97.  
  98.         /////////////////////////////////////////////////////////////////////
  99.  
  100.         create_array(big_array, size_big, s2);
  101.         cout << "Большой массив:" << endl;
  102.         output_array(big_array, size_big);
  103.  
  104.         for (int i = 0; i < size_big; i++)
  105.         {
  106.             big_bubble_array[i] = big_heap_array[i] = big_quick_array[i] = big_array[i];
  107.         }
  108.  
  109.         cout << "Быстрая сортировка Хоара (большой массив):" << endl;
  110.         Hoar_Sort(size_big, big_quick_array);
  111.         output_array(big_quick_array, size_big);
  112.         cout << "Пирамидальная сортировка (большой массив):" << endl;
  113.         Binary_Pyramid_Sort(size_big, big_heap_array);
  114.         output_array(big_heap_array, size_big);
  115.         cout << "Сортировка пузырьком (большой массив):" << endl;
  116.         BubbleSort(size_big, big_bubble_array);
  117.         output_array(big_bubble_array, size_big);
  118.  
  119.         cout << "В быстрой сортировке сравнений: " << compare1 << ", перестановок: " << replace1 << endl;
  120.         cout << "В пирамидальной сортировке сравнений: " << compare2 << ", перестановок: " << replace2 << endl;
  121.         cout << "В сортировке пузырьком сравнений: " << compare3 << ", перестановок: " << replace3 << endl;
  122.  
  123.         if (compare1 < compare2)
  124.             if (compare1 < compare3)
  125.                 cout << "В быстрой сортировке меньше всего сравнений" << endl;
  126.             else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
  127.         else if (compare2 < compare3)
  128.             cout << "В пирамидальной сортировке меньше всего сравнений" << endl;
  129.         else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
  130.  
  131.         if (replace1 < replace2)
  132.             if (replace1 < replace3)
  133.                 cout << "В быстрой сортировке меньше всего перестановок" << endl;
  134.             else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
  135.         else if (replace2 < replace3)
  136.             cout << "В пирамидальной сортировке меньше всего перестановок" << endl;
  137.         else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
  138.  
  139.         cout << "0. Выход" << endl;
  140.         cin >> q;
  141.  
  142.     } while (q != 0);
  143. }
  144.  
  145. void create_array(int* array, int size, string s1)
  146. {
  147.     fstream file_1;
  148.     file_1.open(s1, ios::out);
  149.  
  150.     srand(static_cast<int>(time(0)));
  151.    
  152.     for (int i = 0; i < size; i++)
  153.     {
  154.         file_1 << rand() % 100;
  155.         file_1 << ' ';
  156.     }
  157.     file_1.close();
  158.  
  159.     file_1.open(s1, ios::in);
  160.     for (int i = 0; i < size; i++)
  161.         file_1 >> array[i];
  162.  
  163.  
  164.     file_1.close();
  165. }
  166.  
  167. void output_array(int* array, int size)
  168. {
  169.     for (int i = 0; i < size; i++)
  170.     {
  171.         cout << array[i] << '\t';
  172.         if (!((i + 1) % 20))
  173.             cout << endl;
  174.     }
  175.     cout << endl;
  176. }
  177.  
  178. void Exchange(int i, int j, int* array)
  179. {
  180.     int tmp;
  181.     tmp = array[i];
  182.     array[i] = array[j];
  183.     array[j] = tmp;
  184. }
  185.  
  186. void Hoar_Sort(int size, int* array)
  187. {
  188.     Quick_Sort(0, size - 1, array);
  189. }
  190.  
  191. void Quick_Sort(int left, int right, int* array)
  192. {
  193.     int i, j, m;
  194.     i = left;
  195.     j = right;
  196.  
  197.     m = array[(i + j + 1) / 2];
  198.     do
  199.     {
  200.         while (array[i] < m && compare1++)
  201.             i++;
  202.         while (array[j] > m && compare1++)
  203.             j--;
  204.         if (i <= j)
  205.         {
  206.             Exchange(i, j, array);
  207.             replace1++;
  208.             i++;
  209.             j--;
  210.         }
  211.  
  212.     } while (i <= j);
  213.     if (left < j && compare1++) Quick_Sort(left, j, array);
  214.     if (i < right && compare1++) Quick_Sort(i, right, array);
  215. }
  216.  
  217. void Binary_Pyramid_Sort(int size, int* array)
  218. {
  219.     //преобразование массива в пирамиду
  220.     Build_Pyramid(size / 2 + 1, size - 1, array);
  221.     //сортировка пирамиды
  222.     Sort_Piramid(size - 1, array);
  223. }
  224.  
  225. void Build_Pyramid(int size, int r, int* array)
  226. {
  227.     //просеивание элементов пирамиды
  228.     Sifting(size, r, array);
  229.     if (size > 0)
  230.         //рекурсивно вызываем функцию построения
  231.         Build_Pyramid(size - 1, r, array);
  232. }
  233.  
  234. void Sort_Piramid(int size, int* array)
  235. {
  236.     //переставляем первый элемент пирамиды с последним
  237.     Exchange(0, size, array);
  238.     replace2++;
  239.     //исключаем последний элемент пирамиды
  240.     Sifting(0, size - 1, array);
  241.     //добиваемся того, чтобы массив снова стал пирамидой
  242.     if (size > 1)
  243.         Sort_Piramid(size - 1, array);
  244. }
  245.  
  246. void Sifting(int left, int right, int* array)
  247. {
  248.     //принцип: каждый потомок должен быть меньше, чем родитель
  249.     int q, p;
  250.     q = 2 * left + 1;  //индекс левого элемента
  251.     p = q + 1;  //индекс правого элемента
  252.     if (q <= right && compare2++)
  253.     {
  254.  
  255.         if (p <= right && array[p] > array[q] && compare2++)
  256.             q = p;
  257.  
  258.         if (array[left] < array[q] && compare2++)
  259.         {
  260.             Exchange(left, q, array);
  261.             replace2++;
  262.             Sifting(q, right, array);
  263.         }
  264.     }
  265. }
  266.  
  267. void BubbleSort(int size, int* array)
  268. {
  269.     int i, j, buf;
  270.     for (i = size - 1; i > 0; i--)
  271.         for (j = 0; j < i; j++)
  272.         {
  273.             compare3++;
  274.             if (array[j] > array[j + 1])
  275.             {
  276.                 buf = array[j];
  277.                 array[j] = array[j + 1];
  278.                 array[j + 1] = buf;
  279.                 replace3++;
  280.             }
  281.         }
  282. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement