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

listsorting

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.

Best Answer

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.

Related Topic