Min. No movement from original permutation to destination.
If I understand it correctly, huck_cussler's solution requires finding a position that should go where the empty is.
Here's an alternative solution that requires no lookup and uses a maximum of 2N swaps.
static void swapperSort(int[] arr)
{
int n = arr.length-1;
for(int i=0, pos=0, space=n; i<n-1;)
{
System.out.print(pos + " " + space + " " + Arrays.toString(arr));
if(arr[pos] == pos+1)
{
pos = ++i;
}
else
{
System.out.print(" SWAP");
int idx = arr[pos]-1;
swap(arr, idx, space);
swap(arr, pos, idx);
int tmp = space;
space = pos;
pos = tmp;
}
System.out.println();
}
System.out.println(Arrays.toString(arr));
}
Here's the output for the DAle test case:
0 6 [2, 1, 4, 3, 6, 5, 0] SWAP
6 0 [0, 2, 4, 3, 6, 5, 1] SWAP
0 6 [1, 2, 4, 3, 6, 5, 0]
1 6 [1, 2, 4, 3, 6, 5, 0]
2 6 [1, 2, 4, 3, 6, 5, 0] SWAP
6 2 [1, 2, 0, 4, 6, 5, 3] SWAP
2 6 [1, 2, 3, 4, 6, 5, 0]
3 6 [1, 2, 3, 4, 6, 5, 0]
4 6 [1, 2, 3, 4, 6, 5, 0] SWAP
6 4 [1, 2, 3, 4, 0, 6, 5] SWAP
4 6 [1, 2, 3, 4, 5, 6, 0]
[1, 2, 3, 4, 5, 6, 0]
source to share
First, we need to find all the permutation cycles of the permutation.
A permutation cycle is a subset of a permutation whose elements are traded with each other. For example, in a permutation group
{4,2,1,3}
,(143)
is a 3-cycle and(2)
is a 1-cycle. Here, the notation(143)
means that, starting from the original order{1,2,3,4}
, the first element is replaced by the fourth, the fourth by the third, and the third by the first, that is1 -> 4 -> 3 -> 1
.
Permutation cycles do not overlap and we can count the number of swaps for each cycle independently. Every swap cycle C
with more than one element can be converted to a sorted state |C| + 1
with whitespace swaps (the whitespace will return to its original position at the end). Therefore, the answer to our problem is the total number of elements in all loops with more than one element plus the number of such loops. Note that "the total number of items in all loops with more than one item" is simply the number of items that are not in their places in the permutation.
Example:
p = [3, 4, 1, 6, 5, 2, 8, 7]
cycles = [1, 3], [2, 4, 6], [5], [7, 8]
We don't need to take into account the third loop with one item.
answer = 7 + 3 = 10
All permutation cycles can be found in O(n)
, and the overall complexity of the algorithm will be O(n)
.
source to share
- Toggle an empty item with the first item out of order in the list.
While the list is still unsorted:
- Toggle the space with the number that should go where it is now empty.
You don't need more than O(N)
swaps.
eg. Given S=[3,2,4,1,_]
, 3
is the first element out of order, so replace it with a space to get S=[_,2,4,1,3]
. Now just keep replacing the space with a number that should go where the space is currently, so S=[1,2,4,_,3] -> S=[1,2,_,4,3] -> S=[1,2,3,4,_]
.
In the worst case for the elements 4
, they will all be misplaced, so you need a 1
swap to get the empty one at the first position, then 4
additional swaps to get all the elements in their proper places. In general, worst case for items N
you will need N+1
worst case swaps, so O(N)
.
As pointed out in the comment, the actual question was to find the minimum number of swaps required for a specific list. In case the items are already in order, 0
swaps are of course required . Otherwise (at least two of them are misplaced) you would need one swap for each item that is initially misplaced + 1
at all.
source to share