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

Any array containing possible duplicate elements can be converted to an array that contains only distinct elements in O(n) time: every element is replaced by a pair of elements where the second part of the pair represents the order of occurrence of the element.

For example

3,5,0,3,7,5,3,5

is converted to:

(3,a) , (5,a) , (0,a) , (3,b) , (7,a) , (5,b), (3,c), (5,c)

If a lexicographic order is defined on the new array with pairs, then we have an array of distinct elements.

The minimum number of swaps to sort the new array can be computed in O(n log n) using the well known algorithm from here: https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

Observe that since the second part of the pairs represents the order of occurrence of each element in the original array, the duplicate elements do not have to be sorted in the new array, therefore the number of swaps to sort the new array with the pairs corresponds to the number of swaps to sort the original array.

So, there is an O(n log n) algorithm for counting the number of swaps to sort an array with duplicates, that uses a linear reduction to the distinct-elements case.

Answer 2

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; 
}