Sort from 0 to n - 1#8636

Sort from 0 to n - 1 (Editorial)

Consider the given sequence as a permutation of numbers from $0$ to $n - 1$ n - 1. Represent it as a decomposition into disjoint cycles.

Each cycle can be sorted independently of the others. Let the length of a cycle be $k$ . Then, to place all elements of this cycle into their correct positions, it is sufficient to perform $k - 1$ k - 1 swaps. Indeed, within a cycle, exactly one element can be immediately placed in its correct position, after which a cycle of length $k - 1$ k - 1 remains, and the process continues in the same way.

Now iterate over all indices $i$ from $0$ to $n - 1$ n - 1. If $a_{i} = i$ a_i = i, then the element is already in its correct position and nothing needs to be done. Otherwise, if $a_{i} \neq = i$ a_i \ne i, it means we have found a cycle that has not yet been processed.

Next, we'll "unroll" this cycle. While $a_{i} \neq = i$ a_i \ne i, swap the elements at positions $i$ and $a_{i}$ a_i. After such a swap, the element $a_{i}$ a_i moves to its correct position. By repeating this operation, we fix all elements of the current cycle.

Thus, to find the minimum number of swaps, it is sufficient to:

Decompose the permutation into cycles;
For each cycle of length $k$ , add $k - 1$ k - 1 to the answer.

Example

Consider the second example. The permutation $(4, 0, 3, 2, 1)$ (4, 0, 3, 2, 1) decomposes into two cycles:

$(4, 1, 0)$ (4, 1, 0) of length $3$ ;
$(3, 2)$ of length $2$ ;

The first cycle requires $3 - 1 = 2$ 3 - 1 = 2 swaps, and the second requires $2 - 1 = 1$ 2 - 1 = 1 swap. Thus, the total minimum number of swaps is $2 + 1 = 3$ 2 + 1 = 3.

Algorithm implementation

Store the input permutation in the array $a$ . The performed swaps are stored in the array $an s$ .

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

Read the input permutation.

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

If $a_{i} \neq = i$ a_i \ne i, then process the cycle to which the element $a_{i}$ a_i belongs by performing the necessary swaps. The number of performed swaps is counted in the variable $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++

Print the number of swaps $c n t$ , and then the swaps themselves.

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