How to solve this type of sorting problem? mostly asked in many competition..

Revision en1, by n1e2m3, 2019-05-29 08:36:39

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/

Tags #sorting, google, #medium, searching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English n1e2m3 2019-05-29 08:36:39 886 Initial revision (published)