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.
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:
This would obviously take 3 swaps. (a <=> b, c <=> d, c <=> f)
Applying the algorithm above, it has:
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.
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.