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.
-
$\begingroup$ 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? $\endgroup$Juho– Juho2014年03月30日 11:38:34 +00:00Commented Mar 30, 2014 at 11:38
-
$\begingroup$ @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. $\endgroup$Ilya Gazman– Ilya Gazman2014年03月30日 11:42:45 +00:00Commented Mar 30, 2014 at 11:42
-
$\begingroup$ @Juho I want to find constant $l$ for any given array. $\endgroup$Ilya Gazman– Ilya Gazman2014年03月30日 11:58:14 +00:00Commented Mar 30, 2014 at 11:58
-
$\begingroup$ @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]) $\endgroup$Ilya Gazman– Ilya Gazman2014年03月30日 12:00:11 +00:00Commented Mar 30, 2014 at 12:00
-
$\begingroup$ related: Minimum number of swaps needed to change Array 1 to Array 2? $\endgroup$jfs– jfs2014年03月30日 13:46:20 +00:00Commented Mar 30, 2014 at 13:46
2 Answers 2
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$.
-
$\begingroup$ 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? $\endgroup$Ilya Gazman– Ilya Gazman2014年03月30日 14:18:13 +00:00Commented Mar 30, 2014 at 14:18
-
$\begingroup$ It seems I have misunderstood your question. $\endgroup$Yuval Filmus– Yuval Filmus2014年03月30日 14:56:18 +00:00Commented Mar 30, 2014 at 14:56
-
$\begingroup$ Updated my answer. $\endgroup$Yuval Filmus– Yuval Filmus2014年03月30日 17:46:17 +00:00Commented Mar 30, 2014 at 17:46
-
1$\begingroup$ larc.unt.edu/ian/research/sortingnetworks gives 404 archive: web.archive.org/web/20110816183340/https://larc.unt.edu/ian/… $\endgroup$rofrol– rofrol2020年01月31日 18:17:17 +00:00Commented Jan 31, 2020 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
-
$\begingroup$ For input $n = 4$: output is: [0,1 , 2,3 , 1,3 , 0,2 , 1,2] $\endgroup$Ilya Gazman– Ilya Gazman2014年03月30日 14:13:57 +00:00Commented Mar 30, 2014 at 14:13
-
$\begingroup$ 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) $\endgroup$sjmc– sjmc2014年03月30日 14:27:27 +00:00Commented Mar 30, 2014 at 14:27
-
$\begingroup$ (And off by 3 in the 6 element case) $\endgroup$sjmc– sjmc2014年03月30日 14:40:53 +00:00Commented Mar 30, 2014 at 14:40