allia

критерии 2 сортировки

Oct 26th, 2020 (edited)
1,961
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void merge_series (int **arr, int first, int last_1, int last_2, int *dubl, int *ind, int par)
  8. {
  9.   int i = first;
  10.   int j = last_1+1;
  11.   int c = 0;
  12.  
  13.  for (c = first; c <= last_2; c++)
  14.   if (j > last_2)
  15.     dubl[c] = ind[i++];
  16.      else if (i > last_1)
  17.       dubl[c] = ind[j++];
  18.       else if (arr[ind[i]][par] >= arr[ind[j]][par] && par == 1)
  19.        dubl[c] = ind[i++];
  20.         else if (arr[ind[i]][par] <= arr[ind[j]][par] && par == 2)
  21.          dubl[c] = ind[i++];
  22.           else dubl[c] = ind[j++];
  23. }
  24.  
  25. void sort (int **arr, int first, int last, int *dubl, int *ind, int par)
  26. {
  27.   int middle = (first + last)/2;
  28.  
  29.   if (first < middle)
  30.    sort (arr, first, middle, dubl, ind, par);
  31.   if (middle + 1 < last)
  32.    sort (arr, middle+1, last, dubl, ind, par);
  33.  
  34.   merge_series (arr, first, middle, last, dubl, ind, par);
  35.  
  36.  
  37.   for (int i = first; i <= last; i++)
  38.    {
  39.      ind[i] = dubl[i];
  40.    }
  41. }
  42.  
  43. int main ()
  44. {
  45.   int n;
  46.   int **arr, *ind, *dubl;
  47.   cin >> n;
  48.  
  49.   arr = new int* [n];
  50.   ind = new int [n];
  51.   dubl = new int [n];
  52.  
  53.   for (int i=0; i<n; i++)
  54.     arr[i] = new int [3];
  55.  
  56.   for (int i=0; i<n; i++)
  57.   {
  58.    arr[i][0] = i+1;
  59.    ind[i] = i;
  60.    for (int j=1; j<3; j++)
  61.      cin >> arr[i][j];
  62.   }
  63.  
  64.  sort (arr, 0, n-1, dubl, ind, 1);
  65.  
  66.  int index = 0, shet = 0, i = n-1;
  67.  
  68.  for (int i=0; i<n; i++)
  69.     dubl[i] = 0;
  70.  
  71.  while(i > 0)
  72.     {
  73.       while (arr[ind[i]][1] == arr[ind[i-1]][1] && i > 0)
  74.       {
  75.         index++;
  76.         i--;
  77.       }
  78.       shet = i+1;
  79.        //cout << index << " " << shet << endl;
  80.       if (index != 0)
  81.       {
  82.         sort (arr, shet-1, index+shet-1, dubl, ind, 2);
  83.         index = 0;
  84.       }
  85.       i--;
  86.    }
  87.    
  88.   for (int i=0; i<n; i++)
  89.   cout << ind[i] + 1 << " ";
  90. }
Add Comment
Please, Sign In to add comment