n1e2m3's blog

How to solve this type of sorting problem? mostly asked in many competition..
By n1e2m3, history, 5 years ago, In English

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/

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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)).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But that doesn't ensure minimum number of swaps. For examples consider a = [5, 6, 7, 8, 1, 2, 3, 4]

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry, here we want minimum operation. so, your solution doesn't work. otherwise it is very simple problem.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for your reply.
    i didn't got your approach. can you describe more by taking suitable example?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I am so sorry, I totally missed that the subarrays must be of equal length. Please disregard my above comment.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply