Minimum Swaps to Sort a Permutation
National Olympiad — Regional round (2021 season)
Submission name: swaps.cpp
Problem summary
Find the minimum number of arbitrary two-position swaps needed to sort a permutation of 0…n−1.
Input
n followed by the permutation.
Output
The minimum swap count.
Constraints
2 < n < 100000.
Worked example
Input and output for the worked example discussed below.
Input
5 2 3 0 1 4
Output
2
Solution analysis
- Treat a[i] as the destination index of the value currently at position i. Following these destinations partitions the permutation into disjoint cycles. A position already holding its own index forms a one-element cycle.
- A cycle with k positions can be repaired with k−1 swaps: repeatedly place one value in its correct position. Count each cycle once using a visited array, and add its length minus one.
- For [2,3,0,1,4], the cycles are (0,2), (1,3), and (4). They require 1+1+0=2 swaps. Equivalently the result is n minus the number of cycles.
Why it works
A swap changes the permutation cycle count by at most one. The sorted permutation has n cycles, so at least n−c swaps are needed from c initial cycles. Repairing each k-cycle with k−1 swaps achieves exactly that lower bound.
Complexity: O(n) time and O(n) space: each position is followed once, with the permutation and visited flags stored.
Watch out. The permutation values are 0-based, unlike many graph problems. Count fixed points as cycles, and do not confuse arbitrary swaps with adjacent swaps.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>permutation(n);
for(int&value:permutation){
cin>>value;
}
vector<bool>visited(n,false);
int answer=0;
for(int start=0;start<n;start++){
if(visited[start]){
continue;
}
int length=0;
int current=start;
// Each destination cycle of length k needs exactly k-1 swaps.
while(!visited[current]){
visited[current]=true;
length++;
current=permutation[current];
}
answer+=length-1;
}
cout<<answer<<'\n';
}