Vladislav_Bezruk

Untitled

Oct 26th, 2021
1,296
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. unsigned long long sortTime, asignmentOperations, compareOperations;
  8.  
  9. /* Процедура для преобразования в двоичную кучу поддерева с корневым узлом i,
  10. что является индексом в arr[]. n - размер кучи */
  11. void heapify(int arr[], int n, int i){
  12.     int largest = i;  
  13. // Инициализируем наибольший элемент как корень
  14.     int l = 2*i + 1; // левый
  15.     int r = 2*i + 2; // правый
  16. // Если левый дочерний элемент больше корня
  17.     if (l < n && arr[l] > arr[largest])
  18.         largest = l;
  19. // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
  20.     if (r < n && arr[r] > arr[largest])
  21.         largest = r;
  22. // Если самый большой элемент не корень
  23.     if (largest != i){
  24.         swap(arr[i], arr[largest]);
  25.         heapify(arr, n, largest); // Рекурсивно преобразуем в двоичную кучу затронутое поддерево
  26.     }
  27. }
  28. // Основная функция, выполняющая пирамидальную сортировку
  29. void heapSort(int arr[], int n){
  30.   // Построение кучи (перегруппируем массив)
  31.     for (int i = n / 2 - 1; i >= 0; i--)
  32.         heapify(arr, n, i);
  33.    // Один за другим извлекаем элементы из кучи
  34.     for (int i=n-1; i>=0; i--)
  35.     {
  36.         // Перемещаем текущий корень в конец
  37.         swap(arr[0], arr[i]);
  38.  
  39.         // вызываем процедуру heapify на уменьшенной куче
  40.         heapify(arr, i, 0);
  41.     }
  42. }
  43. void heapSortwithOperations(int arr[], int n) {
  44.     for (int i = 1, j = i; i < n; i++, j = i) {
  45.         while (j > 0 && arr[j] < arr[j - 1]) {
  46.             compareOperations++;
  47.             swap(arr[j], arr[j - 1]);
  48.             asignmentOperations += 3;
  49.             j--;
  50.         }
  51.         compareOperations++;
  52.     }
  53. }
  54. void merge(int arr[], int a, int m, int b) {    
  55.     int i, j, k;  
  56.     int n1 = m - a + 1;    
  57.     int n2 = b - m;    
  58.      
  59.     int lArr[n1], rArr[n2]; //временные массивы
  60.      
  61.     // копировать данные во временные массивы
  62.     for (int i = 0; i < n1; i++)    
  63.         lArr[i] = arr[a + i];    
  64.     for (int j = 0; j < n2; j++)    
  65.         rArr[j] = arr[m + 1 + j];    
  66.      
  67.     i = j = 0; /* начальный индекс первого подмассива и начальный индекс второго подмассива*/    
  68.     k = a;  /* начальный индекс объединенного подмассива */  
  69.      
  70.     while (i < n1 && j < n2) {    
  71.         if (lArr[i] <= rArr[j]) {    
  72.             arr[k] = lArr[i++];      
  73.         } else {    
  74.             arr[k] = rArr[j++];    
  75.         }    
  76.         k++;    
  77.     }    
  78.     while (i < n1) {    
  79.         arr[k++] = lArr[i++];        
  80.     }    
  81.     while (j < n2) {    
  82.         arr[k++] = rArr[j++];      
  83.     }    
  84. }    
  85.  
  86. void mergeSort(int arr[], int a, int b) {  
  87.     if (a < b) {  
  88.         int m = (a + b) / 2;  
  89.         mergeSort(arr, a, m);  
  90.         mergeSort(arr, m + 1, b);  
  91.         merge(arr, a, m, b);  
  92.     }  
  93. }  
  94.  
  95. void mergewithOperations(int arr[], int a, int m, int b) {    
  96.     int i, j, k;  
  97.     int n1 = m - a + 1;    
  98.     int n2 = b - m;    
  99.      
  100.     int lArr[n1], rArr[n2]; //временные массивы
  101.      
  102.     // копировать данные во временные массивы
  103.     for (int i = 0; i < n1; i++) {
  104.         asignmentOperations++;
  105.         lArr[i] = arr[a + i];
  106.     }  
  107.            
  108.     for (int j = 0; j < n2; j++) {
  109.         asignmentOperations++;
  110.         rArr[j] = arr[m + 1 + j];
  111.     }  
  112.      
  113.     i = j = 0; /* начальный индекс первого подмассива и начальный индекс второго подмассива*/    
  114.     k = a;  /* начальный индекс объединенного подмассива */  
  115.      
  116.     while (i < n1 && j < n2) {
  117.         compareOperations++;
  118.         if (lArr[i] <= rArr[j]) {    
  119.             arr[k] = lArr[i++];
  120.             asignmentOperations++;
  121.         } else {    
  122.             arr[k] = rArr[j++];
  123.             asignmentOperations++;  
  124.         }    
  125.         k++;    
  126.     }    
  127.     while (i < n1) {    
  128.         arr[k++] = lArr[i++];
  129.         asignmentOperations++;    
  130.     }    
  131.     while (j < n2) {    
  132.         arr[k++] = rArr[j++];  
  133.         asignmentOperations++;    
  134.     }    
  135. }  
  136.  
  137. void mergeSortwithOperations(int arr[], int a, int b) {  
  138.     if (a < b) {  
  139.         int m = (a + b) / 2;  
  140.         mergeSortwithOperations(arr, a, m);  
  141.         mergeSortwithOperations(arr, m + 1, b);  
  142.         mergewithOperations(arr, a, m, b);  
  143.     }  
  144. }  
  145.  
  146. int getRandom(int max) {
  147.     return rand() % max + 1;
  148. }
  149.  
  150. void generateRandom(int arr[], int n) {
  151.     for (int i = 0; i < n; i++) {
  152.         arr[i] = getRandom(n);
  153.     }
  154. }
  155.  
  156. void generateGrowth(int arr[], int n) {
  157.     for (int i = 0; i < n; i++) {
  158.         arr[i] = i;
  159.     }
  160. }
  161.  
  162. void generateDescending(int arr[], int n) {
  163.     for (int i = 0; i < n; i++) {
  164.         arr[i] = n - i - 1;
  165.     }
  166. }
  167.  
  168. void heapSortBenchmark(int arr[], int n) {
  169.     int bArr[n];
  170.  
  171.     for (int i = 0; i < n; i++)
  172.         bArr[i] = arr[i];
  173.  
  174.     sortTime = clock();
  175.  
  176.     heapSort(bArr, n);
  177.  
  178.     sortTime = clock() - sortTime;
  179.  
  180.     for (int i = 0; i < n; i++)
  181.         bArr[i] = arr[i];
  182.  
  183.     asignmentOperations = compareOperations = 0;
  184.  
  185.     heapSortwithOperations(bArr, n);
  186.  
  187.     cout << "Heap   sort   benchmark" << endl;
  188.     cout << "n = " << n << endl;
  189.     cout << "time = " << sortTime << " milliseconds" << endl;
  190.     cout << "assignment operations = " << asignmentOperations << endl;
  191.     cout << "comparison operations = " << compareOperations << endl;
  192.     cout << "//////////////////////////////" << endl << endl;
  193. }
  194.  
  195. void mergeSortBenchmark(int arr[], int n) {
  196.         int bArr[n];
  197.  
  198.         for (int i = 0; i < n; i++)
  199.                 bArr[i] = arr[i];
  200.  
  201.         sortTime = clock();
  202.  
  203.         mergeSort(bArr, 0, n - 1);
  204.  
  205.         sortTime = clock() - sortTime;
  206.  
  207.             for (int i = 0; i < n; i++)
  208.                 bArr[i] = arr[i];
  209.  
  210.         asignmentOperations = compareOperations = 0;
  211.  
  212.         mergeSortwithOperations(bArr, 0, n - 1);
  213.  
  214.             cout << "Merge   sort   benchmark" << endl;
  215.             cout << "n = " << n << endl;
  216.             cout << "time = " << sortTime << " milliseconds" << endl;
  217.             cout << "assignment operations = " << asignmentOperations << endl;
  218.             cout << "comparison operations = " << compareOperations << endl;
  219.             cout << "//////////////////////////////" << endl << endl;
  220. }
  221.  
  222. void printArr(int *arr, int n) {
  223.     for(int i = 0; i < n; i++) {
  224.         cout << arr[i] << ' ';
  225.     }
  226.     cout << endl;
  227. }
  228.  
  229. int main() {
  230.     int n;
  231.     srand(time(NULL));
  232.  
  233.     int typeN[] = {10, 100, 1000, 10000};
  234.  
  235.     for (int i = 0; i < 4; i++) {
  236.  
  237.         n = typeN[i];
  238.         int *arr = new int[n];
  239.  
  240.         cout << "by random: " << endl;
  241.         generateRandom(arr, n);
  242.         //printArr(arr, n);
  243.         heapSortBenchmark(arr, n);
  244.         mergeSortBenchmark(arr, n);
  245.  
  246.         cout << "by growth order: " << endl;
  247.         generateGrowth(arr, n);
  248.         //printArr(arr, n);
  249.         heapSortBenchmark(arr, n);
  250.         mergeSortBenchmark(arr, n);
  251.  
  252.         cout << "by descending order: " << endl;
  253.         generateDescending(arr, n);
  254.         //printArr(arr, n);
  255.         heapSortBenchmark(arr, n);
  256.         mergeSortBenchmark(arr, n);
  257.     }
  258.     return 0;
  259. }
  260.  
RAW Paste Data