Minimum number of swaps needed to sort an array with duplicate elements

Question

I have come across an algorithm to calculate the minimum number of swaps to sort an array without duplicate elements. The case becomes interesting when there are duplicate elements in the array. Let us assume the array can contain integer elements ranging from -2^31 - (2^31)-1. Also, the array can contain repeated elements in it. Is there an efficient algorithm to find the minimum number of swaps needed to put this array into sorted order?

Note: I'm not actually trying to sort the array, rather to find out the minimum number of swaps that make it in ascending order. I'm not worried about the stability. Swaps can exchange any pair of elements (they need not be adjacent).

Answer 1

int minSwaps(int arr[], int n) 
{ 
    // Create an array of pairs where first 
    // element is array element and second element 
    // is position of first element 
    pair<int, int> arrPos[n]; 
    for (int i = 0; i < n; i++) 
    { 
        arrPos[i].first = arr[i]; 
        arrPos[i].second = i; 
    } 

    // Sort the array by array element values to 
    // get right position of every element as second 
    // element of pair. 
    sort(arrPos, arrPos + n); 

    // To keep track of visited elements. Initialize 
    // all elements as not visited or false. 
    vector<bool> vis(n, false); 

    // Initialize result 
    int ans = 0; 

    // Traverse array elements 
    for (int i = 0; i < n; i++) 
    { 
        // already swapped and corrected or 
        // already present at correct pos 
        if (vis[i] || arrPos[i].second == i) 
            continue; 

        // find out the number of  node in 
        // this cycle and add in ans 
        int cycle_size = 0; 
        int j = i; 
        while (!vis[j]) 
        { 
            vis[j] = 1; 

            // move to next node 
            j = arrPos[j].second; 
            cycle_size++; 
        } 

        // Update answer by adding current cycle.  
        if (cycle_size > 0) 
        { 
            ans += (cycle_size - 1); 
        } 
    } 

// Return result 
    return ans; 
}