allia

критерии 1 сортировка

Oct 28th, 2020
1,203
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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)
  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]][1] > arr[ind[j]][1])
  19.        dubl[c] = ind[i++];
  20.         else if (arr[ind[i]][1] == arr[ind[j]][1])
  21.         {
  22.           if (arr[ind[i]][2] <= arr[ind[j]][2])
  23.           dubl[c] = ind[i++];
  24.           else dubl[c] = ind[j++];
  25.         }
  26.           else dubl[c] = ind[j++];
  27. }
  28.  
  29. void sort (int **arr, int first, int last, int *dubl, int *ind)
  30. {
  31.   int middle = (first + last)/2;
  32.  
  33.   if (first < middle)
  34.    sort (arr, first, middle, dubl, ind);
  35.   if (middle + 1 < last)
  36.    sort (arr, middle+1, last, dubl, ind);
  37.  
  38.   merge_series (arr, first, middle, last, dubl, ind);
  39.  
  40.  
  41.   for (int i = first; i <= last; i++)
  42.    {
  43.      ind[i] = dubl[i];
  44.    }
  45. }
  46.  
  47. int main ()
  48. {
  49.   int n;
  50.   int **arr, *ind, *dubl;
  51.   cin >> n;
  52.  
  53.   arr = new int* [n];
  54.   ind = new int [n];
  55.   dubl = new int [n];
  56.  
  57.   for (int i=0; i<n; i++)
  58.     arr[i] = new int [3];
  59.  
  60.   for (int i=0; i<n; i++)
  61.   {
  62.    arr[i][0] = i+1;
  63.    ind[i] = i;
  64.    for (int j=1; j<3; j++)
  65.      cin >> arr[i][j];
  66.   }
  67.  
  68.  sort (arr, 0, n-1, dubl, ind);
  69.    
  70.   for (int i=0; i<n; i++)
  71.   cout << ind[i] + 1 << " ";
  72. }
RAW Paste Data