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.

  • 4
    Shouldn't this have been asked on SO? – sbi Jan 4 '11 at 11:51
  • 10
    This very much looks like homework... – Xavier Nodet Jan 4 '11 at 12:39
  • 1
    Maybe good for theoretical CS. – Michael K Jan 4 '11 at 15:22
  • Best suits at CS – azam Jan 26 '16 at 9:00
  • 1
    What problem are you trying to solve? – Daenyth Jan 26 '16 at 13:15
up vote 9 down vote accepted

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.

  • 1
    can you explain how does this work on "e d c a b"? According to your theory it will take only 1 swap to sort but actually it needs 3. – Manoj R Jan 4 '11 at 7:57
  • There's 2 subgraphs [e, d, a, b] and [c]. so it's three. I'll update my answer to try to explain the 'enclosed subgraphs' better. – dan_waterworth Jan 4 '11 at 8:11
  • 1
    Thank you for such a thoughtful answer! are there any whitepapers you could point me to? – sova Jan 18 '11 at 2:26
  • 2
    Note that the value could be stated more simply as the length of the list, minus the number of enclosed subgraphs. – augurar Dec 15 '13 at 19:00

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 :)

  • Good! But, you can make it work in O(n) if you create inverted indexes of the elements, instead of checking each time the min of the rest of the array. – azam Jan 26 '16 at 8:59

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

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.

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

  • 1
    Right, but I am interested in calculating the optimal number of swaps for going from ordering A to ordering B regardless of algorithm. Perhaps this is a deeper question than I thought. – sova Jan 4 '11 at 6:22
  • 1
    like i said it depends on the algorithm used. – Pemdas Jan 4 '11 at 6:31

protected by gnat Nov 8 '17 at 15:55

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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