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.

Improve this question
$\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$ Commented 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$ Commented Mar 30, 2014 at 11:42
  • $\begingroup$ @Juho I want to find constant $l$ for any given array. $\endgroup$ Commented 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$ Commented Mar 30, 2014 at 12:00
  • $\begingroup$ related: Minimum number of swaps needed to change Array 1 to Array 2? $\endgroup$ Commented Mar 30, 2014 at 13:46

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Mar 30, 2014 at 14:18
  • $\begingroup$ It seems I have misunderstood your question. $\endgroup$ Commented Mar 30, 2014 at 14:56
  • $\begingroup$ Updated my answer. $\endgroup$ Commented 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$ Commented Jan 31, 2020 at 18:17
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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.