Sorting with a minimal number of swaps

[maxdiver]

The problem is, given an array A[1..N] of numbers (not necessarily different) output a minimal number of swap operations (you can swap any, not only neighbour, elements) needed to make this array sorted.

If all numbers A[i] were different, then the solution is obvious: 1) count the number of inversions, or 2) go through the first element to the last, and if the current element differs from needed - then swap current element with the needed and answer++.

But when there may be several instances of the same number, then difficulties appear: we don't know which of the copies to swap. For example, "2 1 1" - here we should swap 2 and the second 1.


Maybe (I speak about algorithm 2) ), if there are several choices, then we should always swap with the last one?..

[mf]

Did you find this problem at some online judge or contest, or you're just curious?

If all numbers A[i] were different, then the solution is obvious: 1) count the number of inversions

Number of inversions is useful if we are allowed to swap only adjacent elements.

or 2) go through the first element to the last, and if the current element differs from needed - then swap current element with the needed and answer++.

Yeah, that works. And let's try to understand exactly why it works:

Let's draw a directed graph, whose vertex set is the set of elements and there's an edge from each B[i] to A[i], for i=1..N, where B is sorted array A. When all elements are distinct, this graph is a collection of disjoint cycles - it's just the cyclic decomposition of permutation of elements. Each swap either splits a cycle into two (when swapped elements are part of the same cycle), or joins two cycles, and so it either increments or decrements number of cycles. Array becomes sorted when there are n cycles, so the lowest bound on number of swaps is n - c, where c is the initial number of cycles. In the algorithm described above each swap always increases number of cycles, so it achieves this lowest bound.

If elements are not unique, this graph has a lot more complex structure - it can be any Eulerian graph. And it seems to me that minimum number of swaps will be n - c, where c is the maximum number of cycles into which graph's multiset of edges can be partitioned, but this turns out be an NP-hard problem [1]!

[maxdiver]

mf

I'm just curious
I tried to find this problem in online judges, but found only the "easy" version.

Number of inversions is useful if we are allowed to swap only adjacent elements.

Yeah, you're right. It was a wrong move from the algorithm 2) to algorithm 1)

Yeah, that works. And let's try to understand exactly why it works ...

Thanks, I'll think about it...