Sort array with minimum swaps

Question

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) ?

Answer 1

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.

As for your multi-dimensional case, the same idea should work, but you should be more specific about what you mean for a multi-dimensional array to be sorted.