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

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?

• The array length, array elements and return values are all of type int. It doesn't make any sense to use long long int for all local variables; that will just slow down your implementation, which is already a $O(n^2)$ slow algorithm. The optimal solution will scale slower than $O(n^2)$. – AJNeufeld Oct 24 at 18:18

Analyzing the problem, finding clues

I used selection sort approach as selection sort makes minimum swap operation.

Really? (I don't know.) More importantly, are you sure sorting is needed here?

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

When the time limit is exceeded, and the program appears to work correctly for non-large inputs, the typical cause of slowness is the algorithm. It can be hard to find an efficient algorithm. To figure out the trick, look for clues. For example, look details in the question that are not used in the current algorithm.

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

Take a closer look. What's in there that your solution is not using?

There's nothing in your implementation that benefits from integers being consecutive, without any duplicates. That is, it's not benefitting from this constraint on the input:

$$1 \leq arr[i] \leq n$$

In other words, the input consists of the numbers $$\1, 2, 3, ..., n\$$, shuffled. Given such input, you can produce a correct ordering in $$\O(n)\$$. And as such, maybe sorting is not needed here after all.

This is still just a hint, without directly answering how to compute the minimum number of swaps. But this observation must surely be part of the implementation.

(I suggest to stop reading here and try to come up with an algorithm that uses the above observation and implement a passing solution. Continue reading only if you need hints.)

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.

Bugs in questions

I don't recall ever finding a bug in an online puzzle (and that should always be the very last thought on your mind), but this puzzle has one. The 3rd sample input [1, 3, 5, 2, 4, 6, 8] (Testcase 14) violates the constraint $$\1 \leq arr[i] \leq n\$$. The 8 should be replaced with 7. I worked around that by doing this when building indexes:

if (arr[i] > N) arr[i] = N;