# Find the minimum amount of swaps in fixed indices to sort an array

When given the length of a source array, 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, as defined by the following function.

def compare_swap(array, a, b):
if array[a] < array[b]:
(array[a], array[b]) = (array[b], array[a])


Example

• input: 3
• Output: [(0,1), (1,2), (0,1)]

What I mean is something like network sorting.

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

• Your title makes sense, but your example is very confusing. Given an array, do you want to compute the minimum number of swaps to make the input array sorted? – Juho Mar 30 '14 at 11:38
• @Juho Given array length, I want to calculate the minimum amount of swaps to sort array with that length. Also I want to output this data. For that I use array of pairs of indexes that each pair represent a swap. In my example I output such array for input 3, for source array with length of 3. – Ilya Gazman Mar 30 '14 at 11:42
• @Juho I want to find constant $l$ for any given array. – Ilya Gazman Mar 30 '14 at 11:58
• @Juho I define swap as the next method: >>> def compare_swap(array, a, b): ... if array[a] < array[b]: ... (array[a], array[b]) = (array[b], array[a]) – Ilya Gazman Mar 30 '14 at 12:00
• – jfs Mar 30 '14 at 13:46

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$.

• It sound a bit strange as you are saying that I can sort any array with $(n - 1)$ swaps. Or am I missing some thing? – Ilya Gazman Mar 30 '14 at 14:18
• It seems I have misunderstood your question. – Yuval Filmus Mar 30 '14 at 14:56
• Updated my answer. – Yuval Filmus Mar 30 '14 at 17:46
• – rofrol Jan 31 '20 at 18:17

A swap array that will work for any list is $[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01]$. So compare each subsequent pair of elements: this fixes the last element. Then compare each pair excluding the last element: this fixes the second to last element. In all there are $nC2$ comparisons. Your example fits this algorithm for $n=3$.

Edit: however I think this is not minimal

• For input $n = 4$: output is: [0,1 , 2,3 , 1,3 , 0,2 , 1,2] – Ilya Gazman Mar 30 '14 at 14:13
• Well my algorithm would suggest [01, 12, 23, 01, 12, 01]. But I think now my solution is not minimal. The output you suggest looks like the solution here stackoverflow.com/questions/3903086/… . That answer also has solutions with 9 swaps for a 5 element array. I haven't seen the algorithm it uses (and my viewing abilities are limited, I'm on a mobile) so I'm not sure of they are similar to what I've written here (my output uses one additional swap in the 4 and 5 element case) – sjmc Mar 30 '14 at 14:27
• (And off by 3 in the 6 element case) – sjmc Mar 30 '14 at 14:40