How can I find the minimum number of swaps in a consecutive unordered array (vector)?

Question

I am trying to solve a problem:

You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates nor specific order.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.

CONSTRAINTS:

the number of elements must be >= 1

the elements in the array must be <= to the size of the array

My code works when the numbers are not in the right position, but when the element is in the right position it enters an infinite loop, example array: [1 3 5 2 4 6 7] <- My code doesn't work because it gets stuck on 1.

My code:

#include <iostream>
#include <vector>

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

int minimumSwaps(std::vector<int> arr)
{
    int numberOfSwaps = 0;
    int lastElementIndex = (arr.size() - 1);

    bool isSwapping = true;

    while (isSwapping)
    {
        isSwapping = false;
        for (int i = 0; i < arr.size(); i++)
        {
            if (lastElementIndex - (arr.size() - arr[i]) != 0)
            {
                isSwapping = true;
                swap(arr[i], arr[lastElementIndex - (arr.size() - arr[i])]);
                numberOfSwaps++;
            }
            else
            {
                std::cout << arr[i] << " is already in its perfect position." << std::endl;
                
            }
        }
    }

    return numberOfSwaps;
}

P.S: I've just used the else statement to check what was going wrong.

It's not related to the problem: you can use [std::swap](https://en.cppreference.com/w/cpp/algorithm/swap) — Thomas Sablik, Dec 27 '19 at 23:38
`if (lastElementIndex - (arr.size() - arr[i]) != 0)` is equivalent to `if (arr[i] - 1 != 0)`. I don't understand that if condition. Please describe your algorithm. — Thomas Sablik, Dec 27 '19 at 23:50
@ThomasSablik For example [1 3 5 2 4 6 7], `lastElementIndex` is always 6 so `if (lastElementIndex - (arr.size() - arr[i])` is the same as 6 - (7 - 1) = 0 for when `arr[i] == 1`, a value of 0 means it doesn't need to be changed and that's why I only use `swap()` when it's different than 0, so shouldn't the `i` in the loop increase and grab the next element to check if it's on the right position? — João Almeida, Dec 27 '19 at 23:52
You should replace `lastElementIndex` with its constant value `(arr.size() - 1)`. Then you get `if ((arr.size() - 1) - (arr.size() - arr[i]) != 0)` and that is `if (arr[i] != 1)`. — Thomas Sablik, Dec 27 '19 at 23:57
Does this answer your question? [Minimum Swaps 2 - minimum number of swaps required to sort a vector in ascending order](https://stackoverflow.com/questions/59445963/minimum-swaps-2-minimum-number-of-swaps-required-to-sort-a-vector-in-ascending) — Richard Critten, Dec 28 '19 at 00:01
@ThomasSablik `if (arr[i] - 1 != 0)` will be wrong. let's take the array [1 2 5 3 4 6 7] as an instance `if (arr[1] - 1 != 0)` is the same as `if (2 - 1 != 0)` = true for when we check the position of the element 2 in the array. so it'll change its position. but 2 is already in its best position so we don't need to change it — João Almeida, Dec 28 '19 at 00:04
@ThomasSablik the solution you've just given me worked. Thank you — João Almeida, Dec 28 '19 at 00:15
`if (lastElementIndex - (arr.size() - arr[i]) != 0)` and `if (arr[i] - 1 != 0)` are completely equivalent. They will always behave the same. That's probably your problem. I think the condition should be `if (arr[i] - 1 != i)` and not `if (arr[i] != 1)` — Thomas Sablik, Dec 28 '19 at 00:15

score 1 · Accepted Answer · answered Dec 28 '19 at 00:13

Replacing lastElementIndex with its value (arr.size() - 1)

in line

if (lastElementIndex - (arr.size() - arr[i]) != 0)

yields

if ((arr.size() - 1) - (arr.size() - arr[i]) != 0)

and this is equivalent to

if (arr[i] != 1)

That's obviously wrong. Replace the line with

if (arr[i] - 1 != i)

How can I find the minimum number of swaps in a consecutive unordered array (vector)?

1 Answers1