Find the minimum amount of swaps to sort array

Problem Detail: 

When getting source array length, I want to generate the array of swaps that need to be performed in order to sort the source array. I want to make this array as small as possible. Swaps will be performed only if necessary for sorting.

Example

• input: 3;
• Output: [0,1 , 1,2 , 0,1];

I want to understand how to calculate the number of such swaps and how exactly to generate such array.

Edit: Some thing like network sorting.

Asked By : Ilya_Gazman

Answered By : Yuval Filmus

Your question appears to be about sorting networks. Sorting an array in the comparison model requires $\Omega(n\log n)$ comparisons, and so $\Omega(n\log n)$ of your swaps. Ajtai, Komlós and Szemerédi were the first to come up with a matching $O(n\log n)$ sorting network (the AKS sorting network), and their construction was simplified by Patterson. These networks also have the advantage that they can be divided into $O(\log n)$ layers of disjoint swaps. Very recently, Goodrich came up with Zigzag sort, another $O(n\log n)$ sorting network.

Since we know that there exist $O(n\log n)$ sorting networks, we can find an optimal sorting network in time $\binom{n}{2}^{O(n\log n)} = 2^{O(n\log^2 n)}$ (verifying that a network works takes time roughly $2^n$ using the zero-one principle). There is no reason to expect any subexponential algorithm.

You might be interested in Ian Parberry's page on sorting.

---

This part answers the following question: What is the maximal number of swaps needed to order an array of length $n$?

Suppose that your array contained numbers from $1$ to $n$. Then you can think of it as a permutation $\pi \in S_n$. Swapping two elements in the same as multiplying by a transposition, so the question is how many transpositions we need to multiply to get $\pi$. If the cycle structure of $\pi$ is $a_1,\ldots,a_k$ then this number is $(a_1-1) + \cdots + (a_k-1) = n - k$. Therefore $n-1$ is the most that is needed. An example of a permutation needing $n-1$ swaps is $(234\cdots n1)$, which corresponds to the array $2,3,4,\ldots,n,1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23251