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 <puneet.nsi...@gmail.com>wrote:
> @sunny: how do u do it by "Divide n conquer "...can u provide the algo...?
>
>
> On 7/22/11, UMESH KUMAR <kumar.umesh...@gmail.com> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
