Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an array A[1 .. N], which contains N integers.

I need to sort this array.But the only operation that I can perform on array is :

Reverse all elements in some sub-array, which is a consecutive parts of A which 
means choose two integers L and R (1 <= L < R <= N), and swap elements 
A[L] and A[R], A[L+1] and A[R-1], A[L+2] and A[R-2] and so on.

In such operation of L, R, the total cost is R - L + 1. Now i want that array should be sorted by spending minimum cost and also in minimum moves.

Whats the best approach to solve this problem.

Their can be many solution to this problem as this is an optimisation problem.

But what can be a solution near to best possible answer.

EXAMPLE : Let N=6 and array be [2,1,5,4,3,2] Then it can be done in 2 moves

These are : First swap elements in segment [3,6] so the array becomes [2,1,2,3,4,5].Second move is swap elements in segment [1,2] So the final array becomes [1,2,2,3,4,5] Which is sorted array.

share|improve this question
    
This problem seems to be a generalization of a very hard problem of finding optimal sorting networks: en.wikipedia.org/wiki/Sorting_network , although it's possible there is some simplification since it's not a perfect generalization. –  DanielV Mar 12 at 19:25
    
@DanielV Constraints : 1 <= N <= 10000 and 1 <= A[i] <= 5000 –  user3001932 Mar 12 at 19:26
    
Also, are you sure that you want worst case in terms of the array, and not in terms of the length of the array? –  DanielV Mar 12 at 19:27
    
@DanielV I didnt get you ?What you mean by length of array?Do you mean length of segment being reversed ? –  user3001932 Mar 12 at 19:29
    
Among all arrays of length $N$, finding the worst case is easy: [N, 2, N-2, 4, N-4.... 3,N-1,1] is the worst case requiring N/2 swaps. But if you are interested in an algorithm that gives you the optimal result for an array rather than for an array length, that is much harder. PS is this some kind of homework or contest question? –  DanielV Mar 12 at 19:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.