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;
}
comments powered by Disqus