Сортування від 0 до n - 1#8636

Сортування від 0 до n - 1 (Розбір)

Розглянемо задану послідовність як перестановку чисел від $0$ до $n - 1$ n - 1. Представимо її у вигляді розкладання на незалежні цикли.

Кожен цикл можна сортувати незалежно від інших. Нехай довжина циклу дорівнює $k$ . Тоді, щоб поставити всі елементи цього циклу на свої місця, достатньо виконати $k - 1$ k - 1 обмін. Справді, у циклі рівно один елемент можна одразу поставити на правильну позицію, після чого залишається цикл довжини $k - 1$ k - 1, і процес продовжується аналогічно.

Переберемо всі індекси $i$ від $0$ до $n - 1$ n - 1. Якщо $a_{i} = i$ a_i = i, то елемент вже стоїть на своєму місці, і нічого робити не потрібно. Якщо ж $a_{i} \neq = i$ a_i \ne i, значить, ми знайшли цикл, який ще не оброблено.

Далі будемо «розкручувати» цей цикл. Поки $a_{i} \neq = i$ a_i \ne i, виконуємо обмін елементів на позиціях $i$ та $a_{i}$ a_i. Після такого обміну елемент $a_{i}$ a_i стане на своє правильне місце. Повторюючи цю операцію, ми зафіксуємо всі елементи поточного циклу.

Таким чином, щоб знайти мінімальну кількість обмінів, достатньо:

Розкласти перестановку на цикли;
Для кожного циклу довжини $k$ додати $k - 1$ k - 1 до відповіді.

Приклад

Розглянемо другий приклад. Перестановка $(4, 0, 3, 2, 1)$ (4, 0, 3, 2, 1) розкладається на два цикли:

$(4, 1, 0)$ (4, 1, 0) довжини $3$ ;
$(3, 2)$ довжини $2$ ;

Для першого циклу знадобиться $3 - 1 = 2$ 3 - 1 = 2 обміни, для другого $2 - 1 = 1$ 2 - 1 = 1 обмін. Таким чином, загальна мінімальна кількість обмінів дорівнює $2 + 1 = 3$ 2 + 1 = 3.

Реалізація алгоритму

Вхідну перестановку зберігатимемо в масиві $a$ . Виконані обміни зберігаємо в масиві $an s$ .

vector<int> a;
vector<pair<int, int> > ans;

Читаємо вхідну перестановку.

scanf("%d", &n);
a.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Якщо $a_{i} \neq = i$ a_i \ne i, то обробляємо цикл, якому належить елемент $a_{i}$ a_i, виконуючи необхідні обміни. Кількість виконаних обмінів підраховуватимемо у змінній $c n t$ .

for (i = 0; i < n; i++)
  while (a[i] != i)
  {
    ans.push_back(make_pair(i, a[i]));
    swap(a[i], a[a[i]]);
    cnt++;
  }

C++

Виводимо кількість обмінів $c n t$ , а потім самі виконані обміни.

printf("%d\n", cnt);
for (i = 0; i < ans.size(); i++)
  printf("%d %d\n", ans[i].first, ans[i].second);