Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию «пузырьком» работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N−1) раз. Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен Например, наличие в списке пары (4, 1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку. Входные данные 4 1 4 2 3 2 4 3 1 2 Выходные данные 1 2 4 3

#include <iostream>

#include <vector>

#include <cmath>

#include <set>

using namespace std;

void swap(int *a, int *b){

   int temp = *a;

   *a = *b;

   *b = temp;

}

signed main() {

   set<pair<int,int>> s;

   int n;

   cin >> n;

   vector<int> a(n);

   for(int &i:a)

       cin >> i;

   int m;

   cin >> m;

   while(m--){

       int x,y;

       cin >> x >> y;

       s.insert({x,y});

       s.insert({y,x});

   }

   for(int i = 0; i < n; i++)

       for(int j = 0; j < n - i - 1; j++)

           if(a[j] > a[j+1] && s.find({a[j],a[j+1]}) == s.end())

               swap(a[j],a[j+1]);

   for(int &i:a)

       cout << i << " ";

}

int main()

{

using namespace std;

setlocale(LC_ALL, "ru");

srand(time(NULL));

int N = 10, M = 0;

int* parr_1 = new int[N];

int* parr_2 = new int[M];

cout << "Начальный массив: " << endl;

for (int i = 0; i < N; i++)

{

 parr_1[i] = getRandomNumber(-30, 30);

 cout << parr_1[i] << '\t';

 if (parr_1[i] < 0) push_pack(parr_2, M, parr_1[i]);

}

cout << "\n\nОтсортированный массив: " << endl;

bubbleSort(parr_1, N);

for (int i = 0; i < N; i++)

 cout << parr_1[i] << '\t';

cout << "\n\nМассив с отрицательными числами: " << endl;

for (int i = 0; i < M; i++)

 cout << parr_2[i] << '\t';

delete[] parr_1;

delete[] parr_2;

return 0;

}

void push_pack(int *&arr, int& size, const int val)

{

int *newArr = new int[size + 1];

for (int i = 0; i < size; i++)

 newArr[i] = arr[i];

newArr[size++] = val;

delete[] arr;

arr = newArr;

}

int getRandomNumber(const int min, const int max)

{

static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);

return static_cast<int>(rand() * fraction * (max - min + 1) + min);

}

void bubbleSort(int* arr, const int size)

{

int temp = 0;

for (int i = 0; i < size - 1; i++)

{

 for (int j = 0; j < size - 1; j++)

 {

  if (arr[j + 1] < arr[j])

  {

   temp = arr[j + 1];

   arr[j + 1] = arr[j];

   arr[j] = temp;

  }

 }

}

}

int main()

{

using namespace std;

setlocale(LC_ALL, "ru");

srand(time(NULL));

int N = 10, M = 0;

int* parr_1 = new int[N];

int* parr_2 = new int[M];

cout << "Начальный массив: " << endl;

for (int i = 0; i < N; i++)

{

 parr_1[i] = getRandomNumber(-30, 30);

 cout << parr_1[i] << '\t';

 if (parr_1[i] < 0) push_pack(parr_2, M, parr_1[i]);

}

cout << "\n\nОтсортированный массив: " << endl;

bubbleSort(parr_1, N);

for (int i = 0; i < N; i++)

 cout << parr_1[i] << '\t';

cout << "\n\nМассив с отрицательными числами: " << endl;

for (int i = 0; i < M; i++)

 cout << parr_2[i] << '\t';

delete[] parr_1;

delete[] parr_2;

return 0;

}

void push_pack(int *&arr, int& size, const int val)

{

int *newArr = new int[size + 1];

for (int i = 0; i < size; i++)

 newArr[i] = arr[i];

newArr[size++] = val;

delete[] arr;

arr = newArr;

}

int getRandomNumber(const int min, const int max)

{

static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);

return static_cast<int>(rand() * fraction * (max - min + 1) + min);

}

void bubbleSort(int* arr, const int size)

{

int temp = 0;

for (int i = 0; i < size - 1; i++)

{

 for (int j = 0; j < size - 1; j++)

 {

  if (arr[j + 1] < arr[j])

  {

   temp = arr[j + 1];

   arr[j + 1] = arr[j];

   arr[j] = temp;

  }

 }

}

}