Minimum Swaps 2

Minimum swaps possible

Problem Statement

You are given an unordered slice consisting of consecutive integers [3 6 1 7 2 9] without any duplicates. Find the minimum number of swaps required to sort the slice in ascending order.

Problem Considerations

It is in fact another sorting problem, we are given an slice and being tell to sort it in ascending order using the less swaps possible.

Let’s start with a naive but pragmatic approach, looping over the slice and swapping value each time an element is in wrong position.

Minimum swaps

The algorithm

1. The function first creates a slice of pairs slicePairs to store the element alongside their current index. This is done using the sliceMap function, which takes a projection function as input. The projection function in this case is elementIndexPair, which takes the index and the element of the slice and returns a struct eIndexPairs with the index and element as its fields.
2. The slicePairs slice is then sorted in ascending order using the sort package.
3. Next, a boolean array visited is created to keep track of the visited positions in the slice
4. The function then iterates over the slicePairs slice. For each element in the slice, the following steps are performed:

• If the element has already been visited or is at the correct position, the function continues to the next element.
• Otherwise, the function starts a cycle.
• The function iterates over the cycle, swapping the elements at the current position and the element’s index.
• The function marks the current position as visited.
• The size of the cycle is incremented.
• The function breaks out of the cycle when the current position is equal to the element’s index.

5. The function then increments the swaps variable by the size of the cycle.

6. Finally, the function returns the value of the swaps variable.

Minimum swaps in Go

Resources

Minimum Swaps 2 | HackerRank

I ask Google Bard to explain my code