3
$\begingroup$

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.

$\endgroup$
5
  • $\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 Mar 30 '14 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 Mar 30 '14 at 11:42
  • $\begingroup$ @Juho I want to find constant $l$ for any given array. $\endgroup$ – Ilya Gazman Mar 30 '14 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 Mar 30 '14 at 12:00
  • $\begingroup$ related: Minimum number of swaps needed to change Array 1 to Array 2? $\endgroup$ – jfs Mar 30 '14 at 13:46
5
$\begingroup$

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

$\endgroup$
4
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ For input $n = 4$: output is: [0,1 , 2,3 , 1,3 , 0,2 , 1,2] $\endgroup$ – Ilya Gazman Mar 30 '14 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 Mar 30 '14 at 14:27
  • $\begingroup$ (And off by 3 in the 6 element case) $\endgroup$ – sjmc Mar 30 '14 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.