### GRAYRHINO's blog

By GRAYRHINO, history, 16 months ago, Given an array of integers (duplicates are possible), find the minimum number of swaps to sort the array. For [3,9,2,4,2] it should be 2 : [3, 9, 2, 4, 2] -> [2, 9, 3, 4, 2] -> [2, 2, 3, 4, 9]

If the elements are distinct then there's a time complexity O(nlog(n)) and space complexity O(n) solution here. However, I couldn't find any satisfactory proof for solutions where array contains duplicates. So, I have two questions:

1. What is the most optimal solution when all the elements are distinct?
2. Any algorithm when the array contains duplicates?

This seems to be very common questions in top tech interviews. Your ideas and suggestions (possibly code) would be much appreciated.  Comments (12)
 » It's with the same basic principle, let's take the i-th element in the array, we have to swap it (at some point) with the j-th element if, j < i and the i-th element is smaller, or j > i and the j-th element is smaller. this many swaps is necessary as there are at least this many inversions, and we can also see that it is sufficient, so we need to calculate this amount. doing so can be easily done using segment trees, in O(n.log(n)) time and O(n) memory.
•  » » You are counting no of inversions and claiming that answer is no of inversions. It is wrong.He never said you can swap only adjacent elements. In fact answer of this problem is always less than n. While no of inversions can be O(n^2).
•  » » » Thanks for highlighting that. Before posting the question here, I have seen various solutions but almost all of them make some assumptions such as elements are distinct, only adjacent swaps are allowed, etc. While all those assumptions are valid and there's something to learn from them, the reason I posted here is to get feedback for the worst case that is when duplicates are allowed and you can swap any two elements. Hope we can get some satisfactory explanation.
•  » » » » The problem seems interesting but IDK how to solve it. Lebossle wrote about this problem -"you can model it as a graph where nodes are groups of equal elements and edges say where they want to go, which ends up being a circulation (degree in = degree out). The problem is thus decomposition into maximum amount of cycles. Dual is minimum amount of edges to cut to make it a DAG. Not sure how to move from here, I'll think if simplex translates into something fast, like a flow, or maybe it's matroid intersection which I still need to learn"
•  » » » » » Minimum number of edges to cut to make a Graph a DAG is known as the Feedback Arc Set Problem. This is known to be NP-Complete.
 » 16 months ago, # | ← Rev. 2 →   Cycle Sort — Read the second point please. UPD: It is wrong
•  » » 16 months ago, # ^ | ← Rev. 5 →   It's wrong. It goes the correct answer only for a stable sort. Basically, it assumes if i
•  » » Your suggested solution gives 4 for [3,9,2,4,2] and 3 for [5, 1, 3, 2] while for both of them the answer is 2. Am I missing something?