Sorting an array where the only permitted operation is swapping 0 and another element

Question

Given any permutation of the numbers {0, 1, 2,..., N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

This question comes from this website. I've included my code below, which takes too long to solve the problem. How can I solve this efficiently?

#include "stdio.h"
#define MAX 100001  
void swap(int i);
int a[MAX]; 
int m,count=0,zeroindex,next=1;
int check()
{
    int i;
    if(a[0]!=0)
        return -1;
    else
    {
        for(i=next;i<m;i++)
        {
            if(a[i]!=i)
            {
                swap(i);
                next=i;      //just start form the next 
                return -1;
            }
        }       
        return 1;
    }
}

main()
{
int n,i=0,j;
scanf("%d",&m);
for(i=0;i<m;i++)
{
    scanf("%d",&a[i]);
    if(a[i]==0)
        zeroindex=i;
}

while(check()!=1)
{
    for(i=0;i<m;i++)
    {
        if(a[i]==zeroindex)
        {
            swap(i);                    
            break;
        }   
    }
}       
printf("%d",count);
}
void swap(int i)
{
int temp=a[zeroindex];
a[zeroindex]=a[i];
a[i]=temp;
zeroindex=i;
count++;
}

Answer 1

A simple approach:

1. Find all cycles of elements through their original positions.

2. Store size of each cycle in an array L[].

3. Initialise ans = 0.

4. While i = 1 to L.size():
     if A[0] is not included in current cycle:
        ans = ans + L[i] + 1;
     else
        ans = ans + L[i];
     swap elements in array equivalently to correct this cycle.

Answer 2

I think that the optimal solution to this problem involves finding a cycle decomposition of the original array and using that to guide what swaps you make.

There's a convenient notation for representing permutations in terms of smaller cycles within the permutation. For example, consider the array

5 4 0 1 3 2 7 6

The cycle decomposition of this array is (0 2 5)(1 3 4)(6 7). To see where this comes from, start by looking at the number 0. 0 is currently in the position that 2 should occupy. The number 2 is in the spot that 5 should occupy, and 5 is in the position that 0 should occupy. In this sense, the permutation contains a "cycle" (0 2 5) indicating that 0 is in 2's place, 2 is in 5's place, and (wrapping around) 5 is in 0's place. Independently, look at the number 1. 1 is in the spot where 3 should be, 3 is in the spot where 4 should be, and 4 is in the spot where 1 should be. Therefore, there's another cycle (1 3 4) in this permutation. The last cycle is (6 7).

In general, if you're allowed to make arbitrary swaps, the series of swaps required to sort a permutation that uses the fewest number of swaps works by splitting the permutation apart into its cycle decomposition and then using the swaps to repair the permutation. For example, to fix the cycle (0 2 5), the fastest option would be to swap 0 with 5, then swap 5 with 2. (This gives rise to the cycle sort algorithm).

We can adapt this idea here. Going back to our initial array 5 4 0 1 3 2 7 6, which has cycle decomposition (0 2 5)(1 3 4)(6 7), suppose that we want to fix the cycle (1 3 4). To do so, we can do the following:

5 4 0 1 3 2 7 6
5 4 1 0 3 2 7 6    (Swap 0 and 1)
5 4 1 3 0 2 7 6    (Swap 0 and 3)
5 0 1 3 4 2 7 6    (Swap 0 and 4)
5 1 0 3 4 2 7 6    (Swap 0 and 1)

Notice that the elements 1, 3, and 4 are now in the right place. The cycle decomposition of what remains is now (0 2 5)(6 7).

We can fix (6 7) as follows:

5 1 0 3 4 2 7 6
5 1 6 3 4 2 7 0    (Swap 0 and 6)
5 1 6 3 4 2 0 7    (Swap 0 and 7)
5 1 0 3 4 2 6 7    (Swap 0 and 6)

Now 6 and 7 are in the right place, and our remaining cycle decomposition is (0 5 2). That can easily be fixed:

5 1 0 3 4 2 6 7
5 1 2 3 4 0 6 7    (Swap 0 and 2)    
0 1 2 3 4 5 6 7    (Swap 0 and 5)    

More generally, this works as follows. To fix a cycle (c1, c2, ..., cn) that does not contain 0, do the following swaps:

• Swap(0, c1)
• Swap(0, c2)
• Swap(0, c3)
• ...
• Swap(0, cn)
• Swap(0, c1)

To fix a cycle (0, c1, c2, ..., cn), do the following:

• Swap(0, cn)
• ...
• Swap(0, c3)
• Swap(0, c2)
• Swap(0, c1)

The challenge remains to show that this solution is optimal. To do so, let's begin by thinking about the number of swaps made. Suppose that we have a cycle decomposition for the array that contains cycles σ1, σ2, ..., σn. Fixing any individual cycle that does not contain zero requires k + 1 swaps, where k is the number of elements in the cycle. Fixing a cycle that does contain 0 requires k - 1 swaps, where k is the number of elements in the cycle. If we sum this up over all the cycles, we get that the cost is given by the total number of elements that are out of place (call that X), plus the number of cycles (call that C), minus two if 0 happens to be in a cycle (let Z be -2 if zero is out of place and 0 otherwise). In other words, the cost is X + C + Z.

I'm going to claim that there is no possible way to do better than this. Focus on any one individual cycle in the cycle decomposition (and, for simplicity, assume that the cycle doesn't contain zero). To move all of the elements in this cycle back to their original positions, every element in the cycle needs to be moved at least once. Since each swap involves the number 0, the number of total swaps necessary to move every item in the cycle at least once is k, where k is the total number of elements in the cycle. Additionally, we need one more swap because the very first swap we do introduces 0 into the cycle and we need to do another swap to get it out. A similar line of reasoning accounts for why a cycle containing 0 must use at least k - 1 swaps. Overall, this means that the optimal series of swaps is formed by getting the cycle decomposition and using the above approach to swap everything around.

The last question is how to find the cycle decomposition. This, fortunately, can be done efficiently. Let's go back to our original sample array:

5 4 0 1 3 2 7 6

Let's create an auxiliary array mapping each element to its index, which we can fill in in a single pass:

2 3 5 4 1 0 7 6

We can now construct the cycle decomposition as follows. Let's start at 0. The auxiliary array says that 0 is in position 2. Looking at position 2, we see that 2 is in position 5. Looking at position 5, we see that 5 is in index 0. This gives us the cycle (0 2 5). We can repeat this process across the array to build up the cycle decomposition, and from then can just play out the appropriate swaps to sort everything optimally.

Overall, the total time required is O(n), the total space required is O(n), and the number of swaps performed is minimized.

Hope this helps!