Vladislav_Bezruk

Untitled

Oct 20th, 2021
828
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.         swap(arr[0], arr[i]);
  37.  
  38.         // âûçûâàåì ïðîöåäóðó heapify íà óìåíüøåííîé êó÷å
  39.         heapify(arr, i, 0);
  40.     }
  41. }
  42. void heapSortwithOperations(int arr[], int n) {
  43.     for (int i = 1, j = i; i < n; i++, j = i) {
  44.         while (j > 0 && arr[j] < arr[j - 1]) {
  45.             compareOperations++;
  46.             swap(arr[j], arr[j - 1]);
  47.             asignmentOperations += 3;
  48.             j--;
  49.         }
  50.         compareOperations++;
  51.     }
  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]; //temporary arrays  
  60.      
  61.     /* copy data to temp arrays */  
  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; /* initial index of first sub-array and initial index of second sub-array */    
  68.     k = a;  /* initial index of merged sub-array */  
  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]; //temporary arrays  
  101.      
  102.     /* copy data to temp arrays */  
  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; /* initial index of first sub-array and initial index of second sub-array */    
  114.     k = a;  /* initial index of merged sub-array */  
  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. int main() {
  229.     int n;
  230.     srand(time(NULL));
  231.  
  232.     int typeN[] = {10, 100, 1000, 10000};
  233.  
  234.     for (int i = 0; i < 4; i++) {
  235.  
  236.         n = typeN[i];
  237.         int *arr = new int[n];
  238.  
  239.         cout << "by random: " << endl;
  240.         generateRandom(arr, n);
  241.         //printArr(arr, n);
  242.         heapSortBenchmark(arr, n);
  243.         mergeSortBenchmark(arr, n);
  244.  
  245.         cout << "by growth order: " << endl;
  246.         generateGrowth(arr, n);
  247.         //printArr(arr, n);
  248.         heapSortBenchmark(arr, n);
  249.         mergeSortBenchmark(arr, n);
  250.  
  251.         cout << "by descending order: " << endl;
  252.         generateDescending(arr, n);
  253.         //printArr(arr, n);
  254.         heapSortBenchmark(arr, n);
  255.         mergeSortBenchmark(arr, n);
  256.     }
  257.  
  258.     return 0;
  259. }
RAW Paste Data