http://web.mit.edu/~mip/www/probs.html
[12] Sorting by reversals (ONI'04) You are given an array A[1..N]. Your goal is to sort A by the following type of operation: pick some indices i,j and reverse the subarray A[i..j]. Such an operation costs j-i+1, i.e. the length of the portion which is reversed. Your sorting algorithm should have a total cost of O(N lg^2 N). This is a classic problem related to computational biology. To develop a solution, we first find a way to sort sequences of zeros and ones in O(NlgN) time. This is done through a variant of merge sort. First, sort the two halves of the array recursively. Then, the array will look like: 0..01..10..01..1. All we need to do is to reverse the middle two sequences of ones and zeros, which has a cost linear in N. Now we can use this solution as a subroutine to solve the general case. Our algorithm is similar to quicksort, where we partition at each level around the median. To do the partitioning step, we need to move all elements smaller than the median to the left, and all the ones bigger to the right. This is done by marking smaller elements with zero and larger ones with one, and applying the zero-one sorting subroutine. You may find it interesting to think how to use radix sort instead of quick sort for the second part. To do that, you need to find a way to make the subroutine a stable sorting algorithm. On 7/14/06, kingofcoder <[EMAIL PROTECTED]> wrote: > > An array of size N has distinct values 1...N in random order. You have > only operator called rev(X) (where X is any value from 0 to N-1) which > reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets > you 1,3,2,4). Our objective is to sort the array using minimum number > of Rev(X) functions. How many permutations of N size array require > exactly N number of rev(X) operators to get sorted > > a. For size 3 only 1,3,2 requires 3 moves. > > if any body previously posted this questions...iam sorry for that... > actually someone asked me this questions > > i got one solution..but i dont wheather it uses min no of rev func > calls > > PSUEDO CODE :::: > initially i is n; > find max no in [0-i] > rev that function upto max ele position > now max ele in first position > now use rev (i) > now max in nth position > i--; > > now iam finding iteratively next max > > like that iam sorting..... > > > is it efficient solution.. > if any body knows or the gets the more efficient solutions... > > plz tel me... > > Ur frnd > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
