Problem Statement –
The task is to find the minimum number of swaps required in the given arrangement of cartons to get the desired arrangement of cartons. Only adjacent cartons can be swapped.
I have tried an ad hoc approach, but it proved inefficient towards the upper limit of the data range. Here it is for reference –
Traversing through the given arrangement of cartons
if position of carton>than the desired position
swap back
go to previous iteration
What would be a pragmatic approach to the problem?
Test Data Range – N<=105
Source – INOI 2009 Q Paper
6
with only adjacent swaps you are limited to a O(n^2) sorting algorithm, (with worst case being a reverse sorted set)
and since you only have to limit yourself to least amount of swaps you can compare everything as much as you like
one way to guarantee the least amount of swaps is to only swap 2 cartons when they are in reverse order
both bubble sort and insertion sort will do this
the way to compute this minimum is to find the desired location of each carton (with any sorting algo) and take the sum of the amount each carton is shifted and divide by 2
in psuedo code
sort arr
sum=0
foreach c in arr
sum+= abs(oldIndexOf(c)-indexOf(c))
return sum/2
3