So many why's..:) I was just trying to explain the queries about the divide and conquer asked above.+1 to u sunny.
On Fri, Jul 22, 2011 at 1:26 PM, sunny agrawal <[email protected]>wrote: > Yes thats true, > but that will take O(n) extra space in merging step, isn't it ? > and if we have to use O(n) space why dont just use O(n) algorithm !! > > On Fri, Jul 22, 2011 at 1:18 PM, saurabh singh <[email protected]>wrote: > >> For people who like the generic way,its merge sort only difference is >> where comp(a,b) returns true when a%2=1&&a%2=0. >> Rest its same. >> >> On Fri, Jul 22, 2011 at 1:12 PM, sunny agrawal >> <[email protected]>wrote: >> >>> 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. >>> >> >> >> >> -- >> Saurabh Singh >> B.Tech (Computer Science) >> MNNIT ALLAHABAD >> >> >> -- >> 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. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
