Given an array A[1…N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i…(i+k-1)] and A[j…(j+k-1)] such that i+k-1 < j and swap A[i] with A[j], A[i+1] with A[j+1] … and A[i+k-1] with A[j+k-1].
Example:
For n=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ? and what is minimum time complexity ?
hackereath link :
https://www.hackerearth.com/challenges/competitive/japan-national-programming-challenge/approximate/swap-and-sort/description/
What about this solution: copy this array and sort it. Then go through initial array and swap with correct position of this number. Do only swap with only length=1 (k=1). Maximum swaps: O(n), complexity: O(n log(n)).
But that doesn't ensure minimum number of swaps. For examples consider a = [5, 6, 7, 8, 1, 2, 3, 4]
sorry, here we want minimum operation. so, your solution doesn't work. otherwise it is very simple problem.
It's not a full solution but we're looking for a split that removes as many inversions as possible. Once we find that split we can do a Divide and Conquer type approach until we reach a point with no inversions. Now, counting the number of inversions can be perhaps done with a BIT? I don't have any more ideas.
thanks for your reply.
i didn't got your approach. can you describe more by taking suitable example?
Oh, I am so sorry, I totally missed that the subarrays must be of equal length. Please disregard my above comment.
No problem, go ahead.
Are you looking for an optimal solution or a good approximation? If the former, I'm pretty sure the problem is NP so you won't find one and sadly, I'm not good at approximation problems so I can't help much with the latter.
yes, i am looking for optimal solution.
link : https://stackoverflow.com/questions/28741575/minimum-number-of-swap-operations-to-sort-an-array-if-swapping-of-two-equal-size