Advertisement
Marisichka

Untitled

Oct 10th, 2021
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <time.h>
  3. #include <ctime>
  4. #include <stdlib.h>
  5.  
  6. #define n 1000
  7.  
  8. using namespace std;
  9.  
  10. void Merge(int* A, int first, int last, unsigned int& counter_e, unsigned int& counter_m){
  11.     int middle, start, final, j;
  12.     int* mas = new int[n];
  13.     middle = (first + last) / 2;
  14.     start = first;
  15.     final = middle + 1;
  16.     for (j = first; j <= last; j++) {
  17.         if ((start <= middle) && ((final > last) || (A[start] < A[final]))) {
  18.             counter_e++;
  19.             counter_m++;
  20.             mas[j] = A[start];
  21.             start++;
  22.         }
  23.         else {
  24.             counter_e++;
  25.             counter_m++;
  26.             mas[j] = A[final];
  27.             final++;
  28.         }
  29.     }
  30.     for (j = first; j <= last; j++) {
  31.         A[j] = mas[j];
  32.     }
  33.  
  34.     delete[]mas;
  35. };
  36.  
  37. void MergeSort(int* A, int first, int last, unsigned int& counter_e, unsigned int& counter_m) {
  38.     if (first < last) {
  39.         MergeSort(A, first, (first + last) / 2, counter_e, counter_m);
  40.         MergeSort(A, (first + last) / 2 + 1, last, counter_e, counter_m);
  41.         Merge(A, first, last, counter_e, counter_m);
  42.     }
  43. };
  44.  
  45. int main(){
  46.  
  47.     srand(time(NULL));
  48.     int i;
  49.  
  50.     unsigned int counter_e = 0;
  51.     unsigned int counter_m = 0;
  52.  
  53.     int* A = new int[n];
  54.  
  55.     for (int i = 0; i < n; i++) {
  56.         A[i] = rand() % 100;
  57.     }
  58.     clock_t time;
  59.     time = clock();
  60.  
  61.     MergeSort(A, 1, n, counter_e, counter_m);
  62.  
  63.     delete[]A;
  64.  
  65.     time = clock() - time;
  66.  
  67.     cout << "Runtime is " << (double)time / CLOCKS_PER_SEC << endl;
  68.     cout << "Number of comparisons:" << counter_m << endl << " Number of assignments: " << counter_e << endl << endl;
  69.      
  70.     return 0;
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement