# Minimum Swaps

Consider an integer array. What is the minimum number of swaps to sort the array?

• whenever there is a swap, there must be a cycle.
• A swap between two numbers is a cycle of length 2.
• The sort function of the std library of C++ compares the first element of each pair. See the definitions of relational operators: (http://www.cplusplus.com/reference/utility/pair/operators/)
``````#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
int len;
cout << "Enter the length of number array: ";
cin >> len;

pair<int,int> numId[len];
cout << "Enter the numbers" << endl;
for(int i = 0; i < len; ++i)
{
cin >> numId[i].first;
numId[i].second = i;
}

sort(numId, numId+len);

bool visited[len] = {0};
int cycle_len = 0;
int total_swaps = 0;

for(int i = 0; i < len; ++i)
{
int j = i;
if(numId[j].second == j || visited[j]) continue;

while(!visited[j])
{
visited[j] = 1;
cycle_len++;
j = numId[j].second;
}

total_swaps += cycle_len - 1;
cout << total_swaps << endl;
cycle_len = 0;
}

cout << "The minimum number of swaps is " << total_swaps << endl;

return 0;
}
``````