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

Oct 26th, 2020 (edited)
721
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, 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. }
RAW Paste Data