# Sort array with minimum swaps

Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized.

I was thinking of first determining whether it is increasing type or decreasing type i.e. the type in which least swaps would be required and then sort my array in increasing or decreasing order accordingly. I don't know how to implement in determining the type. Can someone help me in finding heuristic or algorithm to do so ?

Also if the array is 2-Dimensional, would the idea still work or will I use less swaps if I change elements between rows instead of within the row itself. And if it has to be inter-row, how would I go about for that such that all rows are sorted (a row can be either increasing or decreasing) ?

Let $A$ be the array; by hypothesis there exists a unique permutation $\pi : A \rightarrow A$ such that $\pi(A)$ is sorted. The minimum number of swaps required to sort $A$ is the minimum $h$ such that there exists a decomposition of $\pi$ in $h$ transpositions.
Certainly $\pi$ can be broken down in at most $n-k$ transpositions where $k$ is the number of cycles in the unique cycle decomposition of $\pi$: it is sufficient to observe that a cycle $(c_1, c_2, \dots, c_l)$ can be rewritten as $(c_1, c_l)(c_1, c_{l-1})\dots(c_1, c_2)$.
It can also be shown that $n-k$ is the minimum, the proof isn't straightforward but it's a known result that you can easily find in literature should you be interested.
• @Buckster: it is not a heuristic but an exact solution. You don't need the cycle decomposition to implement the algorithm: just scan the permutation from left to right, and every time you find a "misplaced" element, swap it with the element that has taken its place. This naive approach runs in $O(n^2)$, but you can bring it down to $O(n)$ if you maintain the inverse permutation. – Anthony Labarre Jan 7 at 13:12