Minimum number of swaps required to sort the array in ascending order

Question

Here is my problem statement. An excerpt:

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array arr = [7, 1, 3, 2, 4, 5, 6] we perform the following steps:

i   arr                     swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

The code:

int minimumSwaps(int arr_count, int* arr) {

long long int i,count=0,j,temp,min,min_index;
for(i=0;i<arr_count;i++)
{
    min=arr[i];
    min_index=i;
    for(j=i+1;j<arr_count;j++)
    {
        if(arr[j]<min)
        {
            min=arr[j];
            min_index=j;
        }
    }
    if(min_index!=i)
    {
        count++;
    temp=arr[min_index];
    arr[min_index]=arr[i];
    arr[i]=temp;
    }
    }
return count;
}

5 out of 15 test-cases are failing. Here is one of the test cases. It is failing with a message as "Terminated due to timeout".

I used selection sort approach as selection sort makes minimum swap operation. My time complexity is O(n^2). Can I reduce it?

Answer 1

Look for clues

My time complexity is \$O(n^2)\$. Can I reduce it?

When the program appears to work correctly for all simple examples you tried, but the time limit is exceeded when you submit, that's a clue indicating that the algorithm is too slow.

Another clue is to ask yourself: are you using all the known information about the input? Look closely at the problem description.

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates.

The current implementation is not using the fact that the input is consecutive integers without duplicates. In other words, the input is basically all the integers 1..n, shuffled.

Alternative algorithm

Consider this algorithm:

• Build an array of indexes of the values in the input: indexes[arr[i] - 1] = i;.
• Iterate over the input array, and when arr[i] != i + 1, then swap arr[i] with arr[indexes[i]], and update the index of the original value of arr[i].

For example, for [7, 1, 3, 2, 4, 5, 6], the content of indexes would be [1, 3, 2, 4, 5, 6, 0] (indexes[7 - 1] = 0; indexes[1 - 1] = 1; indexes[3 - 1] = 2; ....

Then, the content of arr and indexes will go through these changes:

i       = 0; 7 != 1 so swap it with 1 (the element that belongs here)
arr     = [7, 1, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 0]

i       = 1; 7 != 2 so swap it with 2 (the element that belongs here)
arr     = [1, 7, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 1]

i       = 2; 3 == 3 so no swap
arr     = [1, 2, 3, 7, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 3]

i       = 3; 7 != 4 so swap it with 4 (the element that belongs here)
arr     = [1, 2, 3, 4, 7, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 4]

And so on, two more swaps (total 5) and 7 reaches the end.

Answer 2

I have faced the same exam as well, and frank honestly I don't understand how these guys assume that someone who doesn't know algorithm will be able to solve it in timed fashion exam

The answer is you don't need to apply sorting, you need to find number of swaps , this one has better performance rather than Selection algorithm , as it reaches o(log(n)) in performance

The idea is find cycles if a needs to replace b and b needs to replace a then this is a cycle of 2 nodes which requires # of swaps = number of nodes -1

Cycle is when you reach a node that requires to be swapped so a=>b, b=>c, c=>d and d=>c since c requires a swap then this is a cycle, to achieve that we create a boolean array size of n, we loop to find cycles, if an element is checked then we found a cycle, if element is placed in its proper position then this is an element that cycles itself and requires 0 swaps

private static int CheckMinNumberOfSwaps(int[] arr)
    {
        var total = 0;
        var @checked = new bool[arr.Length];

        /* initializing checked array slots to false, it only sets to true if 
           each elmement is placed in its right slot so checked[1] = true 
           indicates that arr[1] = 1. remember this is n+1 series array you 
           can't have value of 9 when array size is less than 9 */ 
        for (var index = 0; index < arr.Length; index++)
        {
            @checked[index] = false;
        }

      
        for (var index = 0; index < arr.Length; index++)
        {
            var entry = arr[index];
            var entryIndex = entry -1;

            if (@checked[entryIndex])
            {
                continue;
            }

            if (entryIndex == index)
            {  //entry is in the right spot
                @checked[entryIndex] = true;
                continue;
            }

            //draw cycle between nodes, we are not doing swapping but we are 
            //counting how many times this element will be swapped before 
            //residing in its proper slot  
            var counter = 0;
            while (!@checked[entryIndex])
            {
                counter++;
                @checked[entryIndex] = true;
                entry = arr[entryIndex];
                entryIndex = entry - 1;
            }

            total += counter -1 ;
        }

        return total;
    }

Answer 3

The code is doing much more work than it needs to.

Reading the problem statement carefully, we just need to calculate how many swaps are required. Actually sorting the array and counting as we go is probably the least efficient way to do this.

I think you really need to abandon this attempt (sorry!) and come up with a more efficient algorithm for counting swaps. As a hint, think of the mapping of current position of an element to its required position, and look for cycles. We know how many swaps it takes to resolve a cycle of length n, and we can just add all those together to get the total.