Divide and Conquer Algorithm : Just like merge Sort of Quick sort.......we just need to modify the merge step of merge sort or Partition step of Quick sort
lets call our this method Arrange(); //just as merge step takes two sorted arrays and make one completely sorted one it takes 2 arrays which are already in the required form (first even nos then odds) then these two arrays will look like EVEN1 ODD1 EVEN2 ODD2 and we need to arrange them as EVEN1 EVEN2 ODD1 ODD2 so we just need to swap middle part or rotate middle part that will take O(n) time in worst case and depth of recursion will be O(lgn) hence O(nlgn) recursive calls will end when size of subarray is less than or equal to 2 i leave it to you how to handle base cases of recursion :) :D Ex. 1,2,3,4 will call to (1,2), (3,4) after solving both the basecases arrays will be (2,1) (4,3) now arrange function will just swap the ODD1 and EVEN2 result will be (2,4,1,3) On Fri, Jul 22, 2011 at 12:36 PM, Puneet Gautam <[email protected]>wrote: > @sunny: how do u do it by "Divide n conquer "...can u provide the algo...? > > > On 7/22/11, UMESH KUMAR <[email protected]> wrote: > > Anybody try for maintain the stable of elements in O(n) as like > > > > Input is :{1,2,3,4,5,6,7} > > then Output should be > > (2,4,6,1,3,5,7) > > not.......... > > > > {2,4,6,1,5,3,7} base on above discussion .................. > > > > -- > > 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?hl=en. > > > > > > -- > 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?hl=en. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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?hl=en.
