Отсортируйте перестановку первых N натуральных чисел, поменяв местами пары, удовлетворяющие заданным условиям.

Дан массив p[] размера N , представляющий собой перестановку первых N натуральных чисел, где N — четное число, задача состоит в том, чтобы отсортировать массив, взяв пару индексов a, b и поменяв местами p[a] и p[ b] в каждой операции, где 2 * |a – b| ≥ Н . Выведите пары индексов, которые меняются местами в каждой операции.

Примеры:

Input: p[] = {2, 5, 3, 1, 4, 6}
Output: 3
1 5
2 5
1 4
Explanation:
Operation 1: Swap p[1] and p[5]. Therefore, p[] modifies to {4, 5, 3, 1, 2, 6}. 
Operation 2: Swap p[2] and p[5]. Therefore, p[] modifies to {4, 2, 3, 1, 5, 6}.
Operation 3: Swap p[1] and p[4]. Therefore, p[] modifies to {1, 2, 3, 4, 5, 6}.
Therefore, the array is sorted.

Input: p[] = {1, 2, 3, 4}
Output: 0

Подход: выполните следующие шаги, чтобы решить проблему:

• Создайте массив posOfCurrNum[] , в котором хранится позиция чисел, представленных в p[] .
• Выполните итерацию в диапазоне [1, N], используя переменную i , и установите для posOfCurrNum[p[i]] значение i .
• Объявите вектор пары и для хранения свопов, которые должны быть выполнены для сортировки данного массива p[] .
• Итерировать в диапазоне [1, N], используя переменную i
  • Если p[i] равно i , это означает, что текущее число i уже присутствует в нужной позиции. Итак, переходим к следующей итерации.
  • Инициализируйте переменную j с помощью posOfCurrNum[i] для хранения текущей позиции числа i .
  • Теперь возникает 4 случая:
    • Случай 1: Если |i – j| * 2 больше n , затем поменяйте местами (i, j) и сохраните эту пару в ans .
    • Случай 2: если n/2 меньше или равно i – 1 , то поменяйте местами (i, 1) → swap(1, j) → swap(i, 1) и сохраните эту пару в ans .
    • Случай 3: если n/2 меньше или равно n – j , тогда swap(i, n) → swap(j, n) → swap(i, n) и сохраните эту пару в ans .
    • Случай 4: если n/2 меньше j -1 и n/2 меньше или равно n – i , то swap(i, n) → swap(n, 1) → swap(1, j) → swap (1, n) → swap(i, n) и сохранить эту пару в ans .
• Выведите размер вектора и .
• Пройдите вектор пар, ans и напечатайте каждую пару.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)