Minimum number of swaps in sorting sequence

Question

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?

I've been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.

My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $a$ to $b$ whenever a value $a$ lies at a position where $b$ should lie in the sorted array ($a \neq b$, so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).

Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?

Answer 1

This problem is known as "sorting strings by interchanges". Amir et al [1] proved that the problem is NP-complete and admits a 1.5-approximation. They also obtain other results for transforming two strings into one another (which is not equivalent to the sorting problem) and using several other cost functions for each transformation.

[1]: Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat: On the Cost of Interchange Rearrangement in Strings. SIAM J. Comput. 39(4): 1444-1461 (2009) -- https://epubs.siam.org/doi/10.1137/080712969

Answer 2

Adding some "trivial" but useful observations to @AnthonyLabarre's answer:

• The number of necessary swaps is can't be less than 0.5 times the number of elements which are not in their "sorted position" (the position they occupy after sorting).
• The number of necessary swaps is can't be more than 1 times the number of elements which are not in their "sorted position".

This is since when you swap one element into its sorted position you're never moving the other element away from its sorted position. The question is only whether you can manage to get "two birds with one stone" a lot, or not.

It also yields a trivial 2-approximation algorithm:

• Determine the sorted positions,
• Repeatedly Swap elements, which are out of their sorted position, into their sorted positions - in any order you like.