How do I figure out the minimum number of swaps to sort a list in-place?

Question

In-place sorting is essentially swapping elements without using extra storage, correct?

How can I find the minimum number of swaps required for a list?

A C D Q R Z   E   // input
| | | > > > <<<   // movement
A C D E Q R   Z   // output

Swapping:

A C D Q R Z E

swap Q with E, ACDERZQ
swap R with Q, ACDEQZR
swap R with Z, ACDEQRZ. done.

3 swaps.

Shifting items left or right is essentially swapping, but I want the optimal number for plucking an item out of line and switching its place with another.

Answer 1

Consider the problem of manipulating a list into a different state where you know the end state.

1. Find each 'enclosed subgraph' bigger than one (I'll explain this later on).
2. Find the sum of the lengths of the subgraphs and subtract the number of subgraphs.
3. There's your answer for the number of swaps.

An 'enclosed subgraph' is a minimal subset of the whole where each item in the initial list is also in the end list.

So if you construct a subgraph with the indices 4,5 and 9 from the initial state and they have the values 10, 20 and 30 then for it to be an 'enclosed subgraph', you should be able to find the values from the end state with the indices 4, 5 and 9 and those values should be 10, 20 and 30 (though not necessarily in that order).

Consider this:

a b c d f e
    |
    v
b a d f c e

This would obviously take 3 swaps. (a <=> b, c <=> d, c <=> f)

Applying the algorithm above, it has:

1. 3 'enclosed subgraphs', ([a,b], [c,d,f], [e])
2. 2 subgraphs with more than one item ([a,b], [c,d,f])
3. There are 5 items in all those subgraphs
4. 5 - 2 == the answer.

It becomes a little more difficult when you want to do the minimal number of swaps to get it into sorted order, however, it is not impossible.

1. Find the sorted order index of each item in the list, if you don't want to move any data, then this is n^2 time.
2. Find the 'enclosed subgraphs'.
3. Swap items in the list to get to the correct order, but only swap items within the same subgraph.

So, I hope you can see it's not impossible to do the minimal number of swaps to get to sorted order, but it's not worth it, because it requires a ridiculous number of comparisons. Just use heapsort.

Answer 2

How about a simple selection sort ?

1. Find the min(A C D Q R Z E)
2. Swap if min() != first element
3. Repeat with (C D Q R Z E)
4. Count the number of swaps.

On your example:

1. A C D are already in order so no swap required.
2. First swap required to put E in place (then array becomes A C D E R Z Q)
3. Q is min of R Z Q, again swap to put it place (then array becomes A C D E Q Z R)
4. R is min of Z R, swap to put in place. (finally array becomes A C D E Q R Z).

... so simple without graphs :)

Answer 3

Most Algorithm listed in Wikipedia is optimized as constant space used, fewest iteration (comparison or code executed-wise). Maybe there are swap-optimized algorithm exists, but not in my knowledge.

Here is a quick solution I come up in mind. (Not Optimal, but good enough answers. You may need to enumerate the solution tree if you need optimal)

1. Identify misplaced node, Let the count be M (Our worst case scenario)
2. Run Several Algorithm and mark the swap they need, cut off if their swap > M
3. Update the minimum M for different algorithm
4. Repeat to 4, until you satisfy

Answer 4

How about this: Every time you swap two elements at indices i and j you record that as a tuple (i,j) somewhere. Once the list is sorted you bust out an abstract algebra book and read up on permutations, more specifically transpositions. There is a canonical cycle decomposition for permutations and once you have the canonical decomposition you can go about figuring out how to extract a minimal set of transpositions from it. I'm thinking of a greedy algorithm where you expand each cycle into a minimal number of transpositions and there should really be only one way of doing this but I'm not sure if this will give the minimal number of transpositions overall. My abstract algebra is not as good as it used to be so you might try asking this question on cs theory stack as well.

Answer 5

Not exactly, additional memory may be used but it is of constant size. computational complexity depends on the algorithm used.