How do I figure out the minimum number of swaps to sort a list in-place?
- by sova
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.
